해시법(체인법, 오픈주소법)

- 해시법(hashing)은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할수 있음

- 배열의 키 값(각 요소의 값)을 배열의 요솟수로 나눈 나머지를 표에 정리한 값을 해시 값(hash value)이라고 하며, 이 해시 값은 데이터에 접근할 때 사용

해시 검색과정)

 1) 해시 함수가 키 값을 해시 값으로 변환

 2) 해시 값을 인덱스로 하는 버킷을 선택

 3) 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색. 키 값과 같은 값을 찾으면 검색 성공. 끝까지 스캔하여 찾지 못하면 검색 실패

요소 추가과정)

 1) 해시 함수가 키 값을 해시 값으로 변환

 2) 해시 값을 인덱스로 하는 버킷을 선택

 3) 버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색. 키 값과 같은 값을 찾으면 키 값이 이미 등록된 상태이므로 추가에 실패. 끝까지 스캔하여 찾지 못하면 리스트의 맨 앞 위치에 노드를 삽입.

요소 삭제과정)

 1) 해시 함수가 키 값을 해시 값으로 변환

 2) 해시 값을 인덱스로 하는 버킷을 선택

 3) 버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색. 키 값과 같응ㄴ 값을 찾으면 그 노드를 리스트에 삭제. 그렇지 않다면 삭제에 실패

---

1. 체인법

- ChainHash :

- ChainHashTester :

---

2. 오픈 주소법

- 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법

- 재해시를 여러번 반복하므로 선형 탐사법(linear probing)이라고도 함

검색과정)

 1) 같은 해시 값의 데이터가 다른 버킷에 저장되어 있으면 재해싱해서 원하는 값을 찾을 때까지 재해시를 반복

- OpenHash :

- OpenHashTester :

이것외에 다른 방식도 있습니다. 나머지는 구글링하시면 알수있습니다.