해쉬 테이블 (Hash Table) - 1

해쉬 테이블이란?

• 키(Key)와 값(value)를 매핑할 수 있는 데이터 구조이다.
• hash function에 key를 입력하면 주소를 리턴받아 value를 저장할 수 있다.
  - 해쉬 함수(Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
  - 해쉬(Hash) : Hash function을 통해 리턴된 고정된 길이의 값으로, 해쉬 값(Hash Value), 해쉬 주소(Hash Address)라고도 한다.
• key를 통해 value가 저장되어있는 주소를 바로 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라진다.
• hash function이 생성할 수 있는 주소에 대한 공간을 배열로 미리 할당한 후, 키에 따른 데이터 저장 및 탐색을 지원한다.
  - 해쉬 테이블(Hash Table) : 키의 연산에 의해 직접 접근이 가능한 데이터 구조
  - 슬롯(slot) : 해쉬 테이블에서 한 개의 값을 저장할 수 있는 공간

해쉬 테이블 생성

public class HashTableOperation {

    public static class HashTable {
        public Slot[] hashTable;

        public HashTable(Integer size) {
            this.hashTable = new Slot[size];
        }

        public class Slot {
            String value;
            Slot(String value) {
                this.value = value;
            }
        }

        public Integer hashFunc(String key) {
            // hashtable의 길이로 나눈 나머지를 주소로 리턴한다면,
            // hashTable의 길이 - 1 만큼의 주소를 만들어낼 수 있으므로,
            // 모든 hashTable의 주소의 공간을 가리킬 수 있다.
            return (int) key.charAt(0) % this.hashTable.length;
        }
    }

    public static void main(String[] args) {
        // Hash Table 선언
        HashTable hashTable = new HashTable(20);
    }
}

해쉬 테이블 데이터 저장 및 추출

public class HashTableOperation {

    public static class HashTable {
        public boolean saveData(String key, String value) {
            Integer address = this.hashFunc(key);

            if(this.hashTable[address] != null) {
                this.hashTable[address].value = value;
            } else {
                this.hashTable[address] = new Slot(value);
            }

            return true;
        }

        public String getData(String key) {
            Integer address = this.hashFunc(key);

            if(this.hashTable[address] != null) {
                return this.hashTable[address].value;
            } else {
                return null;
            }
        }
    }

    public static void main(String[] args) {
        // Hash Table 선언
        HashTable hashTable = new HashTable(20);
        hashTable.saveData("DeanKim", "01012345678");
        hashTable.saveData("WonyoungJang", "01033335555");

        String returnValue = hashTable.getData("DeanKim");

        System.out.println(returnValue);		// 0101234567

    }
}