HashMap (해시맵)

23.07.29

HashMap

 

 

1. HashMap과 Hashtable

1) Set (집합) 과 같이, 순서가 없다.

(순서를 유지 하고 싶으면 ? >> LinkedHashMap 클래스를 사용 하면 된다)

2) 키, 값 한쌍의 형태로 저장 된다.

키는 중복 허용 불가능.
값은 중복 허용 가능.

3) Map 인터페이스를 구현한 대표적인 컬렉션 클래스 이다.

4) HashMap (동기화 X) 은 Hashtable (동기화 O) 의 신버전의 개념 이다.

(동기화 개념은 쓰레드 개념이라, 나중에 다시 정리 하기)

5) TreeMap => TreeSet 과 거의 유사 하다.

범위 검색과 정렬에 유리한 컬렉션 클래스 이다.

HashMap 보다 데이터 추가, 삭제에 시간이 오래 걸리는게 특징 이다.
(비교해 가면서 저장 하기 때문에 ~)

[ 참고 ]

 

2. HashMap의 키 (Key)와 값 (Value)

1) 해싱 (hashing) 기법으로, 데이터를 저장 한다.
데이터가 많아도 검색이 빠른 특징을 가진다.

2) Map 인터페이스를 구현 했다. 데이터를 키와 값의 한쌍으로 저장 한다.

키 (Key) : 컬렉션 내의 키 중에서 유일 해야 한다.
값 (Value) : 키와 달리 데이터의 중복을 허용 한다.

>> 똑같은 키에 다른 값이 들어오면, 에러가 나거나 저장이 안되는게 아니라,
기존의 값에 새로운 값을 덮어 씌우게 된다.

키와 값의 한쌍을 "Entry" 라고 한다.

[ 참고 ]

Object[ ] key; >> 비객체지향적인 코드.
Object[ ] value; >> 비객체지향적인 코드.

---------------------------------------

Entry[ ] table;

class Entry {

Object key;
Object value;
}

>> 객체지향적인 코드.

(JDK 버전이 올라가면서, 내부 코드가 좀 바뀌긴 했는데 개념 정리를 위해서 위와 같이 정리)



3. 해싱 (hashing) 이란 ?

어떤 키 값을 넣으면 해시 함수 (hash function) 가,

해쉬 코드 (배열의 index == 저장 위치) 를 알려 준다.

즉, 해시 함수를 이용해서 해시 테이블에 데이터를 저장 + 검색.

 

4. 해시테이블 이란 ?

데이터를 저장 하는 공간 자체를 해시테이블 이라 한다.

해시테이블은 2차원 배열과 유사하게 생겼다.

그래서 테이블 이라고 부른다.

배열과 다르게, 길이가 가변적인게 차이점 이다.

>> 해시테이블은 배열과 링크드 리스트가 조합된 형태 이다.

 

배열의 장점 : 인덱스만 알면 바로 접근 할 수 있다.
링크드 리스트의 장점 : 가변적이기 때문에 변경에 유리 하다.

(링크드 리스트만 있으면, 인덱스가 없어서 찾기가 어려운데, 배열과 조합해서, 서로의 장점만 부각된 형태)

>> 데이터를 찾을 때, 데이터를 분류 해서 저장한 링크드 리스트를 배열에 저장 해 놓은 형태.     
즉, 해시테이블의 구조라면,
데이터가 많아도 검색 속도가 상당히 빨라지는 이점을 가진다. 성능 굿.



5. [ 정리 ]

해시테이블에 저장된 데이터를 가져오는 과정

1) 키로 해시 함수를 호출해서 해시 코드를 얻는다.
2) 해시 코드 (해시 함수의 반환값) 에 대응 하는 링크드 리스트를 배열에서 찾는다.
3) 링크드 리스트에서 키와 일치하는 데이터를 찾는다.

>>

해시 함수는 같은 키에 대해 항상 같은 해시 코드를 반환 해야 한다.
서로 다른 키일지라도 같은 값의 해시 코드를 반환 할 수도 있다.

 

 

 

6. [ 참고 ] HashMap의 메서드