개념
Hash: 임의 값을 고정 길이로 변환하는 것
Slot: 한 개의 데이터를 저장할 수 있는 공간
Hashing Function: key에 대해 연산을 이용해서 Hash value(Hash address)를 알 수 있는데 이 Hash value(Hash address)가 key에 대한 value가 저장된 공간(slot)과 연결되어 있다.
Hash Table: key에 대한 Hash value(Hash address)에 연결된 공간(slot)에 value를 저장하는 데이터 구조이며, 키 값의 연산에 의해 직접 접근이 가능한 데이터 공간이다. (그래서 key를 통해 데이터를 바로 받아올 수 있으므로 속도가 획기적으로 빨라진다.)
장점
데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
키에 대한 데이터가 있는지 중복 확인이 쉽다.
단점
일반적으로 저장공간이 좀더 필요하다
여러키에 해당하는 주소가 동일ㄹ할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
주요 용도
검색이 많이 필요한 경우
저장, 삭제, 읽기가 빈번한 경우
캐쉬 구현시엔 데이터가 이미 캐쉬에 있냐 없냐를 검사해야하는데 이 때 쓰임 (중복 확인이 쉽기 때문)
리스트 형태의 해쉬 테이블 구현 예제
1. python으로 구현해보기
1) 리스트 변수를 활용한 hash table 구현
사용자의 이름과 핸드폰 번호가 주어졌을 때 사용자의 이름을 hash 처리한 후 이를 key값으로 간주한다.
그리고 hash function을 통해 key값에 대응되는 hash값(hash 주소)을 반환 받고,
이 hash 주소와 연결된 slot에 key에 대한 value로 핸드폰 번호를 저장한다. (즉, 여기선 배열을 hash table로 이용하므로 hash 주소가 배열의 index가 될 것이다. )
hash_table = list([0 for i in range(8)])
def get_key(name):
return hash(name)
def hash_function(key):
return key % 8
def insert(name, phonenumber):
hash_address = hash_function(get_key(name))
hash_table[hash_address] = phonenumber
def retrieve(name):
hash_address = hash_function(get_key(name))
return hash_table[hash_address]2) Collision
1. Chaining 기법
Hash Table 저장공간 외의 공간을 활용하는 Open Hashing기법 중 하나로, 해당 Hashed Value에 이미 값이 있으면 그 뒤에 chain으로 연결시키는 것이다.
※ 그런데 충돌문제를 고려하지 않은 앞선 구현에서는 Hash Table의 Hash_address(Hash value)와 연관된 slot에 value값(phonenumber)만 저장되는 형태로 구현해주었다.
그러나 Hash Collision을 해결하는 두 알고리즘을 구현할 때는 slot에 key와 value값을 모두 넣어주어야 한다.
왜냐하면 아래 그림처럼 key값 없이 value만 넣어준다면
나중에 key값으로 검색시 어떤 것이 내 key값의 value인지 알 수 없기 때문이다.
hash_table = list([0 for i in range(8)])
def get_key(name):
return hash(name)
def hash_function(key):
return key % 8
def insert(name, phonenumber):
key = get_key(name)
hash_address = hash_function(key)
if hash_table[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
if hash_table[hash_address][index][0] == key:
hash_table[hash_address][index][1] = value
return
hash_table[hash_address].append([key, value])
else:
hash_table[hash_address] = [key, value]
def retrieve(name):
key = get_key(name)
hash_address = hash_function(key)
if hash_tablle[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
if hash_table[hash_address][index][0] == key:
return hash_table[hash_address][index][1]
return None
else:
return None2. Linear Probing
chaining을 하다보니 테이블을 써야지 Hash Table의 장점이 사는데, 계속 chaining으로 이어버리기만 한다면 비효율적이다.
그래서 Hash Table 내에서 충돌 문제를 해결하는 Close Hashing 기법 중 하나인 Linear Probing방법은 이미 만들어 놓은 bucket을 먼저 쓰자라는 idea이다.
그래서 충돌이 발생하면 해당 hash_address의 다음 address 부터 맨 처음 나오는 빈 공간의 address 공간에 저장한다.
hash_table = list([0 for i in range(8)])
def get_key(name):
return hash(name)
def hash_function(key):
return key % 8
def insert(name, phonenumber):
key = get_key(name)
hash_address = hash_function(key)
if hash_table[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
if hash_table[index] == 0:
hash_table[index] = [key, value]
return
elif hash_table[index][0] = key:
hash_table[index][1] = value
return
else:
hash_table[hash_address] = [key, value]
def retrieve(name):
key = get_key(name)
hash_address = hash_function(key)
if hash_tablle[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
if hash_table[index] == 0:
return None
elif hash_table[index][0] = key:
return hash_table[index][1]
else:
return None2. JavaScript로 구현해보기
1. resize가 필요없되 collision을 handling 할 수 있는 hash table 함수 구현
문제) Create a hash table with `insert()`, `retrieve()`, and `remove()` methods. The hashtable does not need to resize but it should still handle collisions.
코드)
// getIndexBelowMaxForKey의 결과값인 index를 storage(즉, hash table)의 index라 생각하고,
// storage[index]에 [key, value]를 넣는다.
// storage[index]에 이미 어떤 [key, value]가 들어가 있다면
// 내 key와 같으면 value를 업데이트 해주고
// 아니면 chaining.
// 즉, [ [ [key1, value1], [key2, value2]], , ,[[key3, value3]] ] 이런식이 되도록 구현했다.
// storage bucket tuple
var makeHashTable = function () {
var result = {};
var storage = [];
var storageLimit = 1000;
result.insert = function (key, value) {
// TODO: implement `insert()`
let index = getIndexBelowMaxForKey(key, storageLimit);
const tuple = [key, value];
const bucket = storage[index] || [];
let flag = false;
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value;
flag = true;
}
}
if (flag === false) {
bucket.push(tuple);
}
storage[index] = bucket;
};
result.retrieve = function (key) {
// TODO: implement `retrieve()`
let index = getIndexBelowMaxForKey(key, storageLimit);
const bucket = storage[index];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket[i][1];
}
}
}
return undefined;
};
result.remove = function (key) {
// TODO: implement `remove()`
let index = getIndexBelowMaxForKey(key, storageLimit);
const bucket = storage[index];
if (bucket !== undefined) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket.splice(i, 1);
}
}
}
};
return result;
};
// This is a "hashing function". You don't need to worry about it, just use it
// to turn any string into an integer that is well-distributed between
// 0 and max - 1
var getIndexBelowMaxForKey = function (str, max) {
var hash = 0;
for (var i = 0; i < str.length; i++) {
hash = (hash << 5) + hash + str.charCodeAt(i);
hash = hash & hash; // Convert to 32bit integer
hash = Math.abs(hash);
}
return hash % max;
};
2. resize가 되며 collision을 handling 할 수 있는 hash table 함수 구현
문제) Create a hash table with `insert()`, `retrieve()`, and `remove()` methods.
Be sure to handle hashing collisions correctly.
Set your hash table up to double the storage limit as soon as the total number of items stored is greater than 3/4th of the number of slots in the storage array.
Resize by half whenever utilization drops below 1/4.
코드)
//getIndexBelowMaxForKey의 결과값인 index를 storage(즉, hash table)의 index라 생각하고,
// storage[index]에 [key, value]를 넣는다.
// storage[index]에 이미 어떤 [key, value]가 들어가 있다면
// 내 key와 같으면 value를 업데이트 해주고
// 아니면 chaining.
// 즉, [ [ [key1, value1], [key2, value2]], , ,[[key3, value3]] ] 이런식이 되도록 구현했다.
// storage bucket tuple
var makeHashTable = function () {
var result = {};
var storage = [];
var storageLimit = 1000;
var size = 0;
result.insert = function (key, value) {
// TODO: implement `insert()`
let index = getIndexBelowMaxForKey(key, storageLimit);
const tuple = [key, value];
const bucket = storage[index] || [];
let flag = false;
for (let i = 0; i < bucket.length; i++) {
// console.log('hey');
if (bucket[i][0] === key) {
bucket[i][1] = value;
flag = true;
}
}
if (flag === false) {
bucket.push(tuple);
size++;
}
storage[index] = bucket;
if (size > 0.75 * storageLimit) {
resize(storageLimit * 2);
}
};
result.retrieve = function (key) {
// TODO: implement `retrieve()`
let index = getIndexBelowMaxForKey(key, storageLimit);
const bucket = storage[index];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket[i][1];
}
}
}
return undefined;
};
result.remove = function (key) {
// TODO: implement `remove()`
let index = getIndexBelowMaxForKey(key, storageLimit);
const bucket = storage[index];
if (bucket !== undefined) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
size--;
return bucket.splice(i, 1);
}
}
}
if (size < 0.25 * storageLimit) {
resize(Math.floor(storageLimit / 2));
}
};
function resize(newLimit) {
storageLimit = newLimit;
let oldStorage = storage.slice();
size = 0;
oldStorage.map((bucket) => {
for (let i = 0; i < bucket.length; i++) {
result.insert(bucket[i][0], bucket[i][1]);
}
});
return;
}
return result;
};
// This is a "hashing function". You don't need to worry about it, just use it
// to turn any string into an integer that is well-distributed between
// 0 and max - 1
var getIndexBelowMaxForKey = function (str, max) {
var hash = 0;
for (var i = 0; i < str.length; i++) {
hash = (hash << 5) + hash + str.charCodeAt(i);
hash = hash & hash; // Convert to 32bit integer
hash = Math.abs(hash);
}
return hash % max;
};
reference
패스트캠퍼스 자료구조 이론 <해쉬 테이블>
'Computer Science > Computer Algorithm' 카테고리의 다른 글
| [MIT Algorithm] Hashing 1 (0) | 2023.04.09 |
|---|---|
| 동적 계획법(Dynamic Programming) (0) | 2021.02.13 |
| 정수론 - 소수 (0) | 2020.10.22 |
| 정수론 - 최대공약수, 최소공배수 (유클리드 호제법) (0) | 2020.10.22 |
| DFS (2) | 2020.09.23 |