해시 (hash)
- Hash or HashTable은 내부적으로 배열을 사용해 데이터를 저장한다.
- 해시 알고리즘을 이용해 고유한 인덱스를 얻는다.
- 인덱스를 이용하여 빠른 검색 속도를 갖는다.
- 해시는 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑한 값이다.
해시함수
- 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값이 해시코드, 해시라고 한다.
해시 테이블
- 키와 값을 매핑해둔 데이터 구조.
- 해쉬 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다.
- 동기화를 지원한다.
- key, value에 널 값을 허용하지 않는다.
해시 테이블에 값을 넣는 과정
- 키의 해시 코드 계산
- hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.
- 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리 킬 수 있다.
- 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다.
- 키와 값을 해당 인덱스에 저장한다.
- 충돌에 대비해서 반드시 연결리스트를 이용해야 한다.
물론 데이터가 많이지다보면, 다른 데이터가 같은 해시 값을 가지게 되어 충돌할 수 도 있다.
해시 테이블의 근본적인 문제는 결국 index의 충돌이다.
해시는 원래 데이터가 같으면 해시값도 항상 같다.
그러나 서로 다른 데이터 또한 동일한 해시값을 가질 수 있기에 해시 충돌이 일어난다. -> Hash Collision
해쉬 충돌을 해결하려면? 해쉬 충돌과 해결법
🖐 그럼에도 해시 테이블을 왜 쓸까?
-
적은 자원으로 많은 데이터를 효율적으로 관리하기 위함이다.
-
하드 디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.
-
언제나 동일한 해시 값을 리턴, index를 알면 빠른 검색이 가능해진ㄷ.
-
해시 테이블 시간 복잡도 : O(1) [이진탐색트리는 O(logN)]
HashTable vs HashMap
HashMap
- Map Interface를 implements 한다.
- Map 인터페이스를 구현하기 위해 HashTable을 사용한 클래스.
- key와 value에 널이 허용된다.
- 동기화를 지원하지 않는다.
- 즉, 여러 스레드로부터 안전하지 않다.
- 동기화를 원한다면 ConcurrentHashMap을 사용.(key,value에 null 허용X)
- 반환값이 저장된 요소들의 순회를 위해 Fail-Fast Iterator 반환
- Fail-Fast Iterator : lock이 걸린 상황에서 다른 스레드에서 해당 자료에 요소를 수정하려 한다면 ConcurrentModificationException을 발생시켜 일관성을 보장.
- ConcurrentHashMap은 Map의 복사본을 참조하는 Iterator를 반환하여 다시 반환받은 시점에 Map에 수정이 있을 경우 해당 iterator는 반영되지 않는다. 고로 ConcurrentModificationException은 발생하지 않는다.
- 다중 스레드 상황에서 해당 map의 무결성을 보장한다.
HashTable
- Map Interface를 implements 한다.
- HashMap보다 속도는 느리다.
- key와 value에 널이 허용되지 않는다.
- 동기화를 지원한다.(모든 데이터 변경 메소드가 syncronized로 선언. 그래서 상대적으로 hashmap에 비해 느리기도.)
- 즉, 여러 스레드로부터 안전하다.
- 반환값이 Enumeration 반환
- Enumeration과 Iterator는 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스
developer