알고리즘 공부 [Hash]

Hash 관련되서, 공부를 해보자,

hash는 잘알다 싶이, key-value 로 이루어져 저장하는 구조이다.

key를 기반으로 address를 찾아, value를 저장한다.

 

이를 그냥 저장 할수도 있지만 어떻게 하면 좀 더 잘 이해할수 있을 까

방법은 내가 직접 hash를 구현 해보는 방식이다.

Hash는 Key기준으로 별도 address를 가져온다.

따라서 이 key에 해당 하는 address주소가 어떤 값일지 모르기 떄문에

사용하는 량보다 많은 양의 크기를 가지고 있을 수 밖에 없다.

 

key 기준으로 단순히 value 에 값을 넣는 것은 중복 문제를 가질수 있다.

완벽하게 key기준으로 address를 가져오는 함수를 짜면 문제가 안생기겠지만, 그러기는 사실상 어렵다,

따라서 chaining 기법을 활용하여 해당 값을 저장하는 해쉬를 구현해보자,

 

Chaining방식은 이런 구조로 이루어진다.

key에 대한 address를 가져오는 구조를 가지고, 해당 각각의 노드들은 next 변수를 가지고 있다.

단순히 저장된 주소에 1개에 노드만 담기면 next값이 null이겠지만, 해당 next값이 있다면?

해당 자료구조는 LinkedList처럼 다음 노드를 참조하는 값을 가지고있는다.

코드로 확인해보자

 

 

해당 자료는, Slot이라는 노드를 가지고있고, 최종 myHash class에는 이런 nodelist들을 담는 배열이 들어가게 된다.

처음에 해당 클래스를 생성할때, 이 노드리스트의 배열의 크기대로 값을 생성한다.

단순히 주소를 가져오는 함수를 아래와 같이 구현한다고 가정해보자

이걸 활용해서 저장하는 함수는 아래와 같다.

public void saveValue(String key, String value)
        {
            Integer address = getAdress(key); -> 처음의 주소를 가져온다.
            if(myHashTable[address] != null) -> 해당 주소에 이미 값이 있다면?
            {
                Slot prev = myHashTable[address];
                Slot find = myHashTable[address];
               -> 링크드 리스트의 구조를 가지기 때문에, 해당 신규 값과, 다음 노드를 가르칠 값을 동시에 지정해야한다.
                while(find.next != null) -> 찾는 값의 다음노드가 있다면? 으로 무한 반복을 돌려준다.
                {
                    if(find.key == key) -> 찾는 Slot의 key와 현재 저장하려고하는 key의 값이 같은지를 체크해준다. 만약에 같다면, 기존에                        있는 값을 update하는 개념으로 생각해야한다.
                    {
                        find.value =value;
                        return;
                    -> 업데이트 하는 로직
                    }
                    else{
                        find = find.next;
                        prev = find;
                       -> 만약에 값이 다르다면, 해당 다음 next의 노드를 find로, prev는 마지막으로 탐색한 노드로 값을 넣어줘야한다.
                    }
                }
                prev.next = new Slot(key,value);
                ->while반복 문이 끝났을 경우에는, 해당 prev의 next 값에 신규 Slot을 생성하여 넣어준다.

                    그리고 만약에 find의 next가 없다면 그냥 next에 해당 Slot을 넣어준다
            }
            else
            {
                myHashTable[address] = new Slot(key,value);

                -> 만약에 주소값에 Slot이 없다면 해당 신규 Slot을 넣어준다.
            }
        return;

 

이렇게 하면 넣을때 해당 class의 슬롯 리스트의 값이 있는지, 있다면 해당 값의 next값이 있는지

계속 체크를 하여, 현재 넣으려고하는 Key값과 같은 지를 체크하게 된다.

key값과 같은 값이 있다면, 해당 Slot의 값을 업데이트하고 만약에 없다면 신규 Slot을 넣는다.

 

public String getValue(String key)
    {
        Integer address = this.getAdress(key);
        if(myHashTable[address] == null)
        {
            return null;
        }
        else
        {
            if(myHashTable[address].next != null)
            {
                Slot prev = myHashTable[address];
                Slot find  = myHashTable[address];
                while(find != null)
                {
                 if(find.key == key)
                 {
                     return find.value;
                 }
                 else{
                     prev = find;
                     find =find.next;
                 }
                }
            }
            else{
                return myHashTable[address].value;
            }
            return null;
        }

 

get으로 가져올때는 의외로 심플하다.

배열의 next값을 체크해서, 해당 값이 링크드 리스트인지 체크를 하고, 해당 체크가 필요하면 반복으로 key와 같은지

같다면 해당 value를 return 하고 아니라면 다음 Slot으로 값을 이동시켜준다.

이렇게 되면 값을 정상적으로 가져올수 있다 이방법은 Chaining 방식이면, 충돌을 회피할수있는 해쉬의 구현 방법 중 하나이다.

 

또다른 하나는 라이닝 기법이 있는데, 해당 방법은

저장할때 링크드 리스트의 사용이 아닌, 해당 주소의 값이 비어있지 않다면 다음 주소를 계속 탐색해서 저장

탐색할때는, 해당 주소를 가지고 해당 다음 주소를 계속 탐색 해서 return 하는 방식이다.

이건 구현 하기 쉬워서 패스를 하겠다.

 

요약 해서 이해하면, 해쉬의 핵심 요소는 아래와 같다

 

1. 배열 형태의 index로, 슬롯 리스트를 저장한다,

2. 각 주소를 구하는 함수가 있고, 해당 함수는 배열의 index를 가져올수 있도록한다.

3. Chaining 기법은 해당주소를 가져와서 LinkedList형태인지 체크(노드의 next값이 있는지 체크), LinkedList의 next를 체크

4. 개방주소법은, LinkedList가 아닌, 다음 주소가 null인지 체크를 계속 해서 하면서 해당이 null이라면 값을 넣어준다.