< HashTable >
HashTable 개념
- key와 value를 1:1로 연관지어 저장하는 자료구조
- key가 주어졌을 때, 해당 key에 연관된 value를 조회 가능
- key가 주어졌을 때, 해당 key에 연관된 value를 제거 가능
- 기존 key와 연관된 value가 존재할 때, 새로운 value로 대체 가능
HashTable 구조
- Key, Hash Function, Hash, Value, 저장소(Bucket, Slot)로 구성
Hash Function
- key를 Hash로 바꿔주는 역할
- 해시 충돌을 최대한 피할 수 있도록 함수를 만들어야한다
- Hash Function의 결과가 'Hash'
- Hash를 배열의 인덱스로 사용한다
해시 충돌 해결 방법
- Separating Chaining
- Open addressing
- Resizing
HashTable 장점
- 적은 리소스로 많은 데이터를 효율적으로 관리
- 배열의 인덱스를 사용하여 빠른 검색, 삽입, 삭제 (시간복잡도 O(1))
- Hash와 key에 연관성이 없어 보안 유리
- 중복 제거 쉬움
HashTable 단점
- 해시 충돌 발생 가능
- 공간 복잡도 증가
- 순서 무시
- 해시 함수 의존
HashTable vs HashMap
- HashTable
- 동기
- key-value에 null값 불가 (key는 equals() 사용)
- HashMap
- 비동기
- Key-value에 null값 허용
