해시 테이블

해시 테이블은 연관 배열 구조(associative array)를 이용하여 키(key)와 결과 값(value)을 저장하는 자료구조이다.

연관 배열 구조란 키 1개와 밸류 1개가 일대일 대응으로 연관되어 있는 자료구조이다.

따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.

키와 밸류가 주어졌을 때, 연관 배열에 두 값을 저장하는 명령
키가 주어졌을 때, 연관되는 밸류 값을 얻는 명령
키와 새로운 밸류 값이 주어졌을 때, 키에 연관된 기존 밸류 값에 새로운 밸류 값을 저장하는 명령
키가 주어졌을 때, 해당 키에 연관된 밸류 값을 제거하는 명령

해시 테이블은 키(key), 해시 함수(hash function), 해시(hash), 밸류(value), 저장소(bucket)로 이루어져 있다.

키는 해시 함수를 통해 해시로 변경되고, 해시는 밸류와 매칭되어 저장소에 저장된다.

• 키 (Key): 해시 함수의 input이 되는 고유한 값이며 다양한 길이의 값을 가질 수 있다. 본래의 상태로 최종 저장소에 저장되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.

• 해시 함수 (Hash Function): 키를 해시로 변환하는 역할을 수행한다. 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 관리할 수 있도록 한다. 서로 다른 키가 같은 해시가 되는 경우를 해시 충돌(hash collision)이라 한다.

• 해시 (Hash): 해시 함수의 결과물로 저장소에서 값과 매칭되어 저장된다.

• 밸류 (Value): 저장소에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능하다.

저장 (Insertion)

해시 테이블에서 자료를 저장하기 위해서는 해시 함수를 통해 키를 해시로 변경해야 한다.

저장소 중에 맞는 해시 값을 찾아 해당 밸류를 저장한다.

해시 함수로 해시를 산출하는 과정에서 서로 다른 키가 같은 해시로 변경되는 문제가 발생할 수 있다.

이러한 경우 해시 충돌이라 부르며 키와 밸류가 일대일로 대응되어야 하는 규칙을 위반하기 때문에 문제를 해결해야 한다.

삭제 (Deletion)

저장되어 있는 값을 삭제하는 경우 저장소에서 해당 키와 대응하는 밸류를 찾아 삭제한다.

검색 (Search)

키를 통해 밸류를 찾는 과정은 삭제 과정과 마찬가지로 먼저 키로 해시를 구하고 해시로 밸류를 찾는다.

해시 충돌 (Hash Collision)

서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 되는 문제를 의미한다.

PintOS에서의 해시 테이블

A hash table is represented by struct hash.

struct hash

The hash table operates on elements of type struct hash_elem.

#define hash_entry(elem, type, member)

Each hash table element must obtain a key, the data identifies and distinguishes elements, which must be unique among elements in the hash table.

While an element is in a hash table, its key data must not be changed.

Instead, if need be, remove the element from the hash table, modify its key, then reinsert the element.