[자료구조] 해쉬 테이블(Hash table)

자료구조

HashTable

Key 값에 해싱된 Value를 저장하는 데이터 구조.

출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

Hash

Hash는 일방향 함수이다. 어떤 동일한 값을 함수에 매개변수로 넘긴다면 정해진 하나의 해쉬 값을 도출한다. 하지만 그 역은 구할 수 없다.

Hash 충돌

만약 해쉬 값을 Boolean 자료형으로 한다면 해쉬 값은 50%의 확률로 겹칠 것이다. 이러한 상황을 해쉬 충돌이라 한다.

완전한 해시 함수

어떤 hash 함수가 충돌없이 1:1대응을 할 수 있다면 이를 완전한 해시 함수라 한다.

충돌 극복 방법

1.Open Address
이 방법은 만일 해쉬 충돌이 생긴다면 그 다음 주소에 해당 값을 저장하는 방식으로 사용된다. 하지만 remove 기능을 효율적으로 구현하기 어려운 문제가 생긴다.

2.Separate Chaining
이 방법은 해쉬 충돌이 생길 상황을 대비해 해당 주소에 Linked List를 통해 여러개의 값을 담을 수 있다. JAVA는 기존에 Linked List를 통해서만 이를 구현했지만 이 List가 길어질 상황에 Tree 자료구조로 변경하여 구현하는 방법을 사용하고 있다.

참조
https://d2.naver.com/helloworld/831311