Hash
-
데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
-
해시 함수를 구현하여 데이터 값을 해시 값으로 매핑
-
collision현상 : 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생
Hash Table(Map)
-
key: value로 저장하는 데이터 구조
-
키를 통해 바로 데이터를 받아올 수 있어 속도가 획기적으로 빨라짐
-
데이터가 많아지면 성능이 저하될 수 있음
-
저장할 데이터에 대해 키를 추출할 수 있는 별도 함수도 존재할 수 있음
-
해쉬 : 임의 값을 고정 길이로 변환하는것
-
해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
-
해쉬 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
-
해쉬 값 / 해쉬 주소 : 키를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해뷔 테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 잇음
-
슬롯 : 한 개의 데이터를 저장할 수 있는 공간
장단점
장점
-
배열의 인덱스를 사용해서 검색, 삽입, 삭제가 빠름
-
키와 해시값이 연관성이 없어 보안에도 많이 사용
- 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있음
-
데이터 캐싱에 많이 사용
단점
-
충돌
-
공간 복잡도가 커짐
-
순서가 있는 배열에는 어울리지 않음
-
해시 함수 의존도가 높아짐
사용하는 이유
-
적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
-
하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해짐!
-
언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해짐
-
해시테이블의 시간복잡도 O(1) - (이진탐색트리는 O(logN))
Collision(충돌) 문제 해결
1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)
3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
HashMap vs HashTable
-
자바에서 HashTable과 HashMap의 차이는 동기화 지원 여부
-
HashMap-Null 값 허용
- 병렬 처리를 하지 않을 때(동기화를 고려하지 않는 상황)
-
HashTable-Null 값 허용하지 않음
- 병렬 처리를 할 때(동기화 고려)
-
HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점 존재
-
-
최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있음
