[자료구조] 해쉬 테이블 - JAVA

자료구조 Hash 기본 개념

만약, Hello World와 관련된 010-1234-5678 값을 가지고 오고 싶다고 가정한다.

위와 같은 배열일 때는 배열의[0]부터 [2]까지 넘어와야 찾을 수 있는 반면,
해쉬에서는 Hello World라는 값을 Hash Function을 통해 나온 Integer 형태 값을 통해 Hash Table에 있는 010-1234-5678 값을 바로 불러올 수 있다.
(*해쉬 테이블은 배열로 이뤄져있고, Hash Function에서 나온 정수형 값이 인덱스 역할)

이렇듯, 해쉬는 검색 속도가 빠르다는 장점이 있다.

public class hash {

    public Slot[] hashTable;

    public hash(Integer size){
        this.hashTable=new Slot[size];
    }
    public class Slot{
        String number;
        Slot(String num) {
            this.number = num;
        }
    }
    public int HashFunc(String name){
        return (int)(name.charAt(0))%(name.length());
    }

    public void DataIntoHash(String name,String number){
        Integer Index=this.HashFunc(name);

        if(hashTable[Index]==null){
            /*hash Table 배열의 index 차례에 아무것도 없는 경우
             ->새로운 해쉬 테이블을 만들어 준다*/
            hashTable[Index]=new Slot(number);
        }
        else{
            hashTable[Index].number=number;
            /*그 Index 값에 이미 값이 있다면 값을 변경해준다.*/
        }
    }

}

HashFunction은 개별적으로 정해도 되지만,
나는 (int)(name.charAt(0))%(name.length()) 를 사용해주었다.
(* 첫번째 글자를 아스키코드화하여 이름의 길이만큼 %해주기)



이럴 경우 만약 NAME 을 저장하고 싶을 때
Hello와 Hallo 두 가지(앞 글자의 int형 같고 글자 수 같은 경우)는 어떻게 hash Table 내에 저장이 될까?

다른 데이터가 같은 index 내에 들어가는 Collision이 발생하는 상황이다. 🤢

Collision 해결 방안

위의 코드에서 Slot이 number 값만 알고 있는 것과 달리 key값과 number 값이 일치하는지 알기 위해 Slot에는 key 값이 되는 name 변수와 number 변수 모두 있어야 한다.

1. Linear Proving / 폐쇄 기법

• 해쉬 테이블 내에서 해결하는 폐쇄 기법 : / 다음 빈 Slot을 체크하여 비어진 Slot에 값을 저장한다.

   public class Slot{
        String number;
        String name;
        Slot(String key, String num) {
            this.number = num;
            this.name=key;
        }
    }
    public int HashFunc(String name){
        return (int)(name.charAt(0))%(name.length());
    }

    public void DataIntoHash(String name,String number){
        Integer Index=this.HashFunc(name);
        
        if(hashTable[Index]==null){
            /*hash Table 배열의 index 차례에 아무것도 없는 경우
             ->새로운 해쉬 테이블을 만들어 준다*/
            hashTable[Index]=new Slot(name,number);
        }
        
        else{
            if(hashTable[Index].name==name){
                hashTable[Index].number=number;
                /*만약, 일치하는 name이 있다면, number 값만 바꿔준다*/
            }
            else{
            /*이름이 겹치지 않는 경우, 
            먼저 같은 index 크기를 가진 다른 name이 있으므로 index를 이동해야 한다.*/
                Index+=1;
                while(Index<hashTable.length){
                    if(hashTable[Index]==null){
                        hashTable[Index]=new Slot(name,number);
                        break;
                    }
                    else{
                        if(hashTable[Index].name==name) {
                            hashTable[Index].number = number;
                            break;
                        }
                        else
                            Index+=1;
                    }
                }
            }
        }
    }

2. Chaining / 개방 기법

• 중복되는 Slot에서 링크드리스트 기법으로 연결시켜준다.

  public hash(Integer size){
        this.hashTable=new Slot[size];
    }
    public class Slot{
        String number;
        String name;
        Slot next;
        Slot(String key, String num) {
            this.number = num;
            this.name=key;
            this.next=null;
        }
    }
    public int HashFunc(String name){
        return (int)(name.charAt(0))%(name.length());
    }
    public void InsertData(String name,String number){
        Integer Index=this.HashFunc(name);
        if(hashTable[Index]==null)
            hashTable[Index]=new Slot(name,number);
        /*Index가 비어있다면 새로운 Slot을 추가해준다*/
        else{
            Slot find=this.hashTable[Index];
            while(find.next!=null){
                if(find.name==name)
                    find.number=number;
                else{
                    find=find.next;
                }
            }
            find.next=new Slot(name,number);
        }

    }