자료구조) 해쉬테이블(Hash Table)

해쉬테이블(Hash Table)

검색하고자 하는 키값을 입력받아서 해쉬 코드를 통해서 Index를 변환해서 저장소에 있는 Value를 받는 방법이다.

해쉬 코드의 가장 장점은 검색 속도가 빠르다.

해쉬 함수로 만든 해쉬 코드는 정수로 치환해서 해당 인덱스와 직접 인덱싱이 된다.

빅오 표기법으로는 O(1)이지만 실제 collision에 의거해서 O(n)

여러 가지 검색 로직에 의거해서 검색하는 게 아니고 실제 자료 번지에 대한 정보로

직접 접근이기 때문에 속도가 빠르다.

Hash Algorithm을 통해서 저장소에 있는 공간을 생성하는 과정이 있는데 Hash Algorithm의 성능에 따라 조금 차이가 있다.

해쉬 테이블 구현한 코드는 다음과 같다.

public class Node{
    string m_strKey;
    string m_strValue;

    public Node(string _key, string _value){
        this.m_strKey = _key;
        this.SetValue( _value );
    }
    public string value(){
        return this.m_strValue;
    }
    public void SetValue(string _value){
        this.m_strValue = _value;
    }

    public string key(){
        return this.m_strKey;
    }
}

public class CustomHashTable 
{
    LinkedList<Node> [] data;


    #region Private Method
    #endregion
    
    #region Public Method
    public CustomHashTable(int _size){
        this.data = new LinkedList<Node>[_size];
    }

    public int GetHashCode(string key){
        int hashcode = 0;
        char []list = key.ToCharArray();
        for(int i = 0; i< list.Length;i++ ){
            hashcode+=list[i];
        }
        return hashcode;
    }

    int convertToIndex(int _hashcode){
        return _hashcode % data.Length;
    }
    public Node searchKey(LinkedList<Node> _list, string _key){
        Node returnValue = null;
        
        if(null == _list){
            return returnValue;
        }

        var enumertor = _list.GetEnumerator();
        while(enumertor.MoveNext()){
            Node node = enumertor.Current;
            if(node.key().Equals(_key)){
                return node;
            }
        }

        return returnValue;
    }

    public void put(string _key, string _value){
        int hadcode = this.GetHashCode(_key);
        int index = this.convertToIndex(hadcode);

        Logger.LogFormat("[HashTable] key :{0}, hashcode[{1}] index : {2}", _key, hadcode, index);
        LinkedList<Node> list = this.data[index];
        if(null == list){
            list =new LinkedList<Node>();
            data[index]= list;
        }


        //중복
        Node node = this.searchKey(list, _key);
        if(null == node ){
            list.AddLast(new Node(_key,_value));
        }
        else{
            node.SetValue(_value);
        }
    }

    public string getValue(string _key){
        int hadcode = this.GetHashCode(_key);
        int index = this.convertToIndex(hadcode);
        LinkedList<Node> list = this.data[index];
        Node node = this.searchKey(list, _key);

        return (null == node)? "Not Found" : node.value();
    }
    #endregion
}

해쉬 테이블에 대한 데이터를 입력 및 테스트 코드이다.

 CustomHashTable hash = new CustomHashTable(3);
        hash.put("1","A");
        hash.put("2","B");
        hash.put("3","C");
        hash.put("1","AA");

        for(int i = 0; i < 4;i++){
            Logger.LogFormat("[Hash Test] Key : {0} : Value : {1}",i, hash.getValue(i.ToString()));
        }

테스트한 결과는 다음과 같다.

키 포인트는 데이터의 길이를 기준으로 인덱싱 기준을 잡고

중복되는 (해쉬 충돌 aaa = 3 / bbb = 3 일경우) 경우에는 내부에서 선형 검색을 진행한다는 점이다.