해시법

해시법

해시법 : '데이터를 저장할 위치' (= 인덱스) 를 간단한 연산으로 구하는 것을 말한다.

키	5	6	14	20	29	34	37	51	69
해시값 (키 % 13)	5	6	1	7	3	8	11	12	4

 

여기서 각각의 키를 13으로 나눈 값이 인덱스가 된다.

키를 해시값으로 변환하는 과정을 해시 함수라 하고,
해시 테이블에서 만들어진 인덱스를 버킷이라고 한다.

해시 테이블을 크게 만들면 충돌 발생 없지만 메모리 낭비 + 느리다.
해시 테이블 작게 만들면 충돌 발생하지만 검색, 추가, 삭제할 때 빠르다.

 

해시 충돌

위에 있는 해시 테이블에 18 넣으면 18 % 13 == 5 이므로 인덱스가 5가 되어야 한다.
하지만 인덱스 5는 자리가 이미 차 있다.

이렇게 인덱스가 중복되는 것을 해시 충돌이라 한다.

 

해시충돌 대처법

• 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.
• 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

 

체인법

 

체인법에서는 중복값 나오면 노드로 연결해서 따로 뺀다.