해싱
해시함수를 사용하여 key값(매핑 전 데이터 값)을 hash값(매핑 후 데이터 값)으로 매핑하는 과정이다.
해시 함수
데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
해시 테이블
정의
해시함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스 혹은 주소 삼아 value값을 키와함께 저장하여 검색을 빠르게 하기위한 자료구조이다.
key,value로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다. hash function 한번만 수행하면 저장된 array의 index 위치를 알아낼 수 있기 때문에 데이터의 저장과 삭제가 매우 빠르다.(랜덤 access가 가능한 array의 장점과 크기 조절이 자유로운 LinkedList의 장점이 합쳐진것) 단점으로는 데이터가 저장되기 전에 공간을 미리 만들어 놔야되기 때문에 공간에 채워지지 않는 경우가 발생한다. 그리고 collision이 일어날 수 있다.
내부의 bucket이라는 데이터 저장소의 사이즈만큼 나눈 나머지(나머지는 무조건 나누는 수 이하의 값이 나오므로)를 index로 쓴다. 이때 collision이 발생할 수도 있다.
bucket과 slot
bucket : 해시테이블의 각 엔트리
slot : key-value pair가 저장되는 버킷의 단위 하나의 bucket에는 여러개의 slot이 있을 수 있다.
slot이 여러개라면 탐색의 시간복잡도가 O(n)이 될 수 있지 않을까?
라는 생각이 들어서 okky에도 질문해보고 옛날에 썼던 두꺼운 전공책도 펼쳐보았다😂
slot의 개수인 s 값은 대부분의 경우 작기 때문에 (내부메모리테이블의 경우 대부분 s는 1임) 버킷 내 탐색을 위해서 순차 탐색 기법을 이용할 수 있다고 한다.
해시 충돌 (Hash Collision)
해시함수는 대게 해시값의 개수보다 더 많은 키값을 변환하므로 해시함수가 서로 다른 두개의 키에 대해 동일한 해시값을 내는 해시충돌이 발생하게 된다.
충돌이 일어날 가능성이 있음에도 해시테이블을 쓰는 이유
적은 데이터를 효율적으로 관리하기 위해서.
하드디스크나 클라우드에 존재하는 많은 데이터들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐시 메모리로도 프로세스를 관리할 수 있게 됨.
충돌을 완화하는 방법이 두가지 있다.
1. 해시 테이블의 구조 개선
Chaining
충돌이 발생했을 때 이를 동일한 버킷에 저장하는데 이를 연결리스트 형태로 저장하는 방법을 말한다. 삽입은 여전히 O(1)이 걸리지만 탐색과 삭제의 경우 최악 O(K)가 걸릴 수 있다. (K는 key의 개수)
Open Addressing (개방 주소법)
해시값으로 얻은 주소나 인덱스 값에 데이터가 꽉차있다면 다른 주소를 이용할 수 있게하는 기법이다. 다음 인덱스로 이동하여 비어있는 곳에 저장한다. 탐색은 계산한 해시값에 대한 인덱스부터 검사하며 탐사(Probing)해나가는데 이 때 삭제 표시가 되어있는 부분은 지나간다. 삭제는 탐색을 통해 해당 값을 찾고 삭제한 뒤 삭제 표시를 한다. 삭제된 공간은 DummySpace로 활용되는데 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다고 한다.
Open Addressing 구현 방법
- Linear Probing : 현재 버킷 인덱스로 부터 고정 폭 만큼씩 이동하여 차례대로 비어있는 버킷을 찾아서 저장함
- Quadratic Probing : 해시 저장 순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생 할 경우 1만큼 이동하고 그 다음 계속 충돌이 일어나면 2^2, 3^2 칸씩 옮겨가는 방식이다.
- Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 다른 방법보다 더 많은 연산을 하게 된다.
Chaining 과 Open Addressing의 장단점
chainning은 삭제 작업이 간단하다. 삭제작업이 빈번하다면 chaining 선택
OpenAddressing은 데이터의 크기가 작을 수록 성능이 더 좋다. 데이터의 크기가 작다면 OpenAddressing 선택
2. 해시 함수 개선
- 나눗셈법 : 해시테이블 크기(N)를 알때 K mod N을 해시값으로 사용하는 방법
- 곱셈법 : 0<A<1인 A에 대하여 KA의 소수점 이하 부분을 N과 곱하면 0과 N사이 값이 된다.
레퍼런스
