해싱은 모든 길이의 데이터 요소를 고정 크기 키에 매핑할 수 있는 방법입니다. 해싱은 키-값 쌍으로 작동합니다.
해싱 함수는 해시 맵에서 매핑을 수행하는 함수입니다. 해시 함수에 대한 입력으로 제공된 데이터 요소는 동일한 해시 키를 얻을 수 있습니다. 이 경우 요소가 겹칠 수 있습니다. 동일한 해시 키를 가진 요소가 겹치는 것을 방지하기 위해 체인 개념이 도입되었습니다.
해시맵 생성
해시맵을 생성하려면 데이터 요소의 인덱스 값을 정의할 해시 함수가 필요합니다.
n개의 버킷이 있는 해시 테이블이 있습니다. 해시 테이블에 노드를 삽입하려면 , 해시 함수는
로 제공됩니다.hashIndex =키 % noOfBuckets
이제 이 해시 함수를 사용하여 해시맵에 삽입된 모든 값의 해시 인덱스를 계산합니다. .
-
요소를 삽입하고 주어진 키 값의 hashIndex를 계산한 다음 목록의 끝에 새 노드를 삽입합니다.
-
노드를 삭제하기 위해 해시 인덱스를 계산하고 해시 인덱스에 해당하는 버킷에서 버킷의 요소를 검색하여 제거합니다.
예시
#include<iostream>
#include <list>
using namespace std;
class Hash{
int BUCKET;
list < int >*table;
public:
Hash (int V);
void insertItem (int x);
void deleteItem (int key);
int hashFunction (int x){
return (x % BUCKET);
}
void displayHash ();
};
Hash::Hash (int b){
this->BUCKET = b;
table = new list < int >[BUCKET];
}
void Hash::insertItem (int key){
int index = hashFunction (key);
table[index].push_back (key);
}
void Hash::deleteItem (int key){
int index = hashFunction (key);
list < int >::iterator i;
for (i = table[index].begin (); i != table[index].end (); i++){
if (*i == key)
break;
}
if (i != table[index].end ())
table[index].erase (i);
}
void Hash::displayHash (){
for (int i = 0; i < BUCKET; i++){
cout << i;
for (auto x:table[i])
cout << " --> " << x;
cout << endl;
}
}
int main (){
int a[] = { 5, 12, 67, 9, 16 };
int n = 5;
Hash h (7);
for (int i = 0; i < n; i++)
h.insertItem (a[i]);
h.deleteItem (12);
h.displayHash ();
return 0;
} 출력
0 1 2 --> 9 --> 16 3 4 --> 67 5 --> 5 6