[Data Structure] HashTable

HashTable

- (key, value)로 데이터를 저장하는 자료구조

- 빠른 검색 속도

• 내부적으로 bucket을 사용해서 데이터를 저장
• bucket : 실제 값이 저장되는 장소

- 각각의 key값에 해시함수를 적용해서 bucket의 고유한 index를 생성해서 index를 활용해서 값을 저장/검색

• index = key.hashCode()%capacity

- O(1) 

- capacity : bucket의 크기 (16)

- load_factor = 저장된 데이터 개수 / capacity

 

 

※ Example

("John Smith", "521-1234") 데이터를 capacity(16)인 HashTable에 저장하면

• index = hash_function("John Smith")%16
• bucket[index] = "521-1234"로 전화번호 저장

 

Hash_Function

1. Division Method 

• 나눗셈을 이용해서 입력값을 테이블의 크기로 나눠서 계산
• 주소 = 입력값 % 테이블의 크기
• 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용하면 효과가 좋다

 

2. Digit Folding

• key의 문자열을 ASCII 코드로 바꾸고, 값을 합한 데이터를 테이블 내의 주소로 사용
• hash_index = (short)(key ^ (key>>16))

 

3. Multiplication Method

• 숫자로 이루어진 key값 K, 해시 테이블의 크기 M(소수 prime number)
• h(K) = K mod M

 

4. Univeral Hashing

• 다수의 해시함수를 만들어서 집합 H에 넣어두고, 무작위로 선택해서 해시값 생성