Hash Table

hash table이란 키를 이용하여 값을 찾아가는 구조를 의미한다 구성 요소로는 아래와 같다

• key
• value
• hash function
• hash value

예를 들어 key1과 value1 이렇게 한 쌍의 데이터가 있을 때 이 key1을 hashFunction에 대입하여 나온 hash value( 10 )를 인덱스로 하는 표에 value1을 저장한다.

Hash Method

• insert : hash table에 삽입하는 함수

    function insert(key,value,table){
    //index=hashFunction(key);
    //table[index]=value;
    }

• search : key에 해당하는 value를 찾아주는 함수

    function search(key,table){
    //index=hashFunction(key);
    //return table[index]
    }

• remove : key에 해당하는 위치에 있는 value를 hashtable 에서 삭제하는 함수

    function remove(key,table){
    //index=hashFunction(key);
    //delete table[index]
    }

• hashFunction

해쉬 함수의 다음과 같은 요구 사항을 충족할 수 록 좋은 함수이다

1. 계산하기 쉬운 함수

2. 균일하게 key를 분포하는 함수

3. 같은 위치의 hash value가 적게 나오는 함수

   function hashFunction(key){
   //return key값을 가공해서 리턴한다
   }

충돌 해결 방식

충돌이란 hash 함수를 거쳐서 나온 hash value가 이미 존재하는 경우를 말한다 이를 해결하기 위해 여러가지 방법이 있지만 일반적인 방법으로 hash table의 value를 저장하는 곳을 연결 리스트로 구현하여 충돌이 발생하면 충돌이 발생한 위치의 value의 다음 노드에 다른 value를 저장한다