Hash(해쉬)

Java.Util 사용하지 않고 Hash구현

https://www.swexpertacademy.com/main/code/referenceCode/referenceCodeDetail.do?referenceId=HASH&category=DataStructure

HashTable Class

public class HashTable {

    class Hash{
        String key;
        String data;
    }

    int capacity = 0;
    Hash[] table;


    /**
     * 생성자
     * @param capacity
     */
    public HashTable(int capacity){
        this.capacity = capacity;
        table = new Hash[capacity];

        for(int i=0; i<capacity; i++) {
            table[i] = new Hash();
        }
    }


    private int hash(String str){
        int hash = 5381;
        for(int i=0; i<str.length(); i++){
            int c=  (int)str.charAt(i);
            hash = ( (hash << 5)+hash ) + c;
        }
        if(hash < 0) hash *= -1;
        return hash % capacity;
    }


    public String find(String key){ 
        int h = hash(key);
        int cnt = capacity;

        while( table[h].key!=null && (--cnt)!=0  ){ //비어있지 않음 && 한바퀴 이상돌지않음 -> 다음칸 탐색

            if(table[h].key.equals(key)){
                return table[h].data;
            }
            h = (h+1) % capacity;
        }
        return null;
    }


    boolean add(String key, String data){
        int h = hash(key);
        while( table[h].key != null){ //비어있지 않음 -> 다음칸 탐색

            if( table[h].key.equals(key) ) return false; //해당 키는 이미 사용됨
            h = (h+1) % capacity;
        }
        table[h].key = key;
        table[h].data = data;
        return true;
    }
}

open adressing방식.

<< : 쉬프트연산( http://egloos.zum.com/js7309/v/11128720 )

h = (h+1) % capacity

다음칸을 탐색하는데, 최대 크기를 넘어서면 다시 한바퀴 돌게 된다.

Main Class

import java.util.Scanner;

public class Main {

    static int MAX_TABLE = 4096;

    public static void main(String[] args) throws Exception{

        Scanner sc  = new Scanner(System.in);
        int T = sc.nextInt();
        for(int test_case = 0; test_case<T; test_case++){

            HashTable hashTable = new HashTable(MAX_TABLE);
            int N = sc.nextInt();

            for(int i=0; i<N; i++){

                String key = sc.next();
                String data = sc.next();
                hashTable.add(key, data);
            }
            System.out.printf("#%d\n", test_case);

            int Q = sc.nextInt();
            for(int i=0; i<Q; i++){
                String key = sc.next();
                String findedData = hashTable.find(key);

                if(findedData!=null) System.out.printf("%s\n", findedData);
                else System.out.println("not find\n");

            }
        }
        sc.close();

    }
}