Java-자료구조 (Hash Table)

1. 해쉬 테이블

• 키(Key)에 데이터(Value)를 매핑할 수 있는 구조
• 해싱 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
• Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐
• 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색을 지원한다.

2. 알아둘 용어

• 해쉬 함수(Hash Function): 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
  • 해쉬(Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(hash Address): 해싱 함수를 통해 리턴된 고정된 길이의 값
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 슬롯(Slot): 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간
  

3. 간단한 해쉬

3-1. hash table 클래스 만들기

* 참고 ( 객체 배열 )

• 객체 배열 선언시, 각 배열의 아이템은 각 객체를 참조할 수 있는 주소를 담을 수 있는 공간만 할당
  • 각 아이템 생성시, 별도로 각 객체를 생성해줘야 함
  • 즉, 객체 배열 선언시, 각 생성할 객체를 가리킬 주소만 저장할 공간을 배열로 만드는 것임

public class main {
    public static void main(String[] args) {
        Students[] students = new Students[5];

        for(int i = 0; i < students.length; i++) {
            students[i] = new Student("00" + i, "홍길동" + i, "남자", (double)((int)(new Random().nextDouble() * 4.5 * 100)) / 100));
        }
        for(int i = 0; i < students.length; i++) {
            System.out.println("---------------");
            students[i].show();
        }
    }
}

// 이와같이 객체 배열을 만들 수 있다.

---

// src/com.company.Hash/Hash.java

package com.company.Hash;

public class MyHash {
    public Slot[] hashTable;

    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }

    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }
}

3-2. 초간단 해쉬 함수를 만든다

• Key가 문자열일 떄, 문자열의 앞 글자를 숫자로 변환해서, Division기법을 사용하여, Key에 대한 주소(인덱스 번호)계산
  • Division 기법: 가장 간단한 해쉬 함수 중 하나로, 나누기를 통해, 나머지 값을 사용하는 방법

3-3. 해쉬 테이블 클래스에 해쉬 함수 추가

// src/com.company.Hash/Hash.java

package com.company.Hash;

public class MyHash {
    public Slot[] hashTable;

    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }

    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
}

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

Slot[] hashTable = new Slot[20];
System.out.println(hashTable[0]);
// null

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

Slot[] hashTable = new Slot[20];
hashTable[0] = new Slot("test");
System.out.println(hashTable[0]);
System.out.println(hashTable[0].value);

// REPL.$JShell$40$Slot@5a20858a
// test

해시 테이블 클래스에 saveData()메서드 추가

// src/com.company.Hash/Hash.java

package com.company.Hash;

public class MyHash {
    public Slot[] hashTable;

    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }

    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }

    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;
    }
}

해쉬 테이블 클래스에 key에 대한 데이터를 가져오는 메서드 추가

// src/com.company.Hash/Hash.java

package com.company.Hash;

public class MyHash {
    public Slot[] hashTable;

    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }

    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }

    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;
        }
    }
}

완성된 해시테이블 테스트

// src/com.company/Main.java

package com.company;

import com.company.Hash.MyHash;

public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        System.out.println(mainObject.getData("HyunseoLee"));
    }
}

// 01044445555

4. 자료 구조 해쉬 테이블의 장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

5. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

기존 알고리즘의 문제점

// src/com.company/Main.java

package com.company;

import com.company.Hash.MyHash;

public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        mainObject.saveData("David", "01066667777");
        mainObject.saveData("Dave", "01088889999");
        System.out.println(mainObject.getData("DaveLee"));
    }
}

// 01088889999

5-1. Chaining 기법

• 개방 해싱 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 방법

// src/com.company.Hash/MyHash.java

package com.company.Hash;

public class MyHash {
    public Slot[] hashTable;

    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }

    // 내부 클래스
    public class Slot {
        public String key;
        public String value;
        public Slot next;

        public Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }

    public boolean saveData(String key, String value) {
        // 해당 키에 대한 주소를 가져온다.
        Integer address = this.hashFunc(key);

        // 이미 해당 슬롯이 있다면
        if(this.hashTable[address] != null) {
            // linked list 기법을 사용해서 이어 붙여야 한다.
            // 일종의 해드라고 할 수 있다.
            Slot findSlot = this.hashTable[address];
            while(findSlot.next != null) {
                if(findSlot.key == key){
                    // 해당되는 키를 찾았다면 value만 바꿔주면 된다.
                    findSlot.value = value;
                    return true;
                } else {
                    findSlot = findSlot.next;
                }
            }
            // 만약 마지막까지 순회했다면
//            System.out.println("findSlot key >> " + findSlot.key);
//            System.out.println("findSlot value >> " + findSlot.value);
//            System.out.println("key >> " + key + " value >> " + value);
            findSlot.next = new Slot(key, value);
        } else {
            // 해당 슬롯에 아무것도 할당되어 있지 않다면
            this.hashTable[address] = new Slot(key, value);
        }
        return true;
    }


    public String getData(String key) {
//        System.out.println("we're just find >> " + key);
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            Slot findSlot = this.hashTable[address];
            while(findSlot != null) {
//                System.out.println("Slot key >> " + findSlot.key);
//                System.out.println("Slot value >> " + findSlot.value);
                if(findSlot.key == key) {
                    return findSlot.value;
                } else {
                    findSlot = findSlot.next;
                }
            }
            return null;
        } else {
            return null;
        }
    }
}

// src/com.company/Main.java

package com.company;

import com.company.Hash.MyHash;

public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        mainObject.saveData("David", "01066667777");
        mainObject.saveData("Dave", "01088889999");
        System.out.println(mainObject.getData("Dave"));
    }
}

// 01088889999

5-2. Linear Probing 기법

• 폐쇄 해싱 또는 Close Hashing 기법중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

// src/com.company.Hash/MyHash.java

package com.company.Hash;

public class MyHash {
    public Slot[] hashTable;

    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }

    // 내부 클래스
    public class Slot {
        public String key;
        public String value;
        public Slot next;

        public Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }


    // Linear Probing 기법
    public boolean saveData(String key, String value) {
        // 해당 키에 대한 주소를 가져온다.
        Integer address = this.hashFunc(key);

        // 값이 있다면
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                this.hashTable[address].value = value;
                return true;
            } else {
                // linear probing기법을 위해 address를 1더 해준다
                Integer currAddress = address + 1;
                while(this.hashTable[currAddress] != null) {
                    if(this.hashTable[currAddress].key == key) {
                        this.hashTable[currAddress].value = value;
                        return true;
                    } else {
                        currAddress++;
                        if(currAddress >= this.hashTable.length) {
                            return false;
                        }
                    }
                }
                this.hashTable[currAddress] = new Slot(key, value);
                return true;
            }
        } else {
            this.hashTable[address] = new Slot(key, value);
        }
        return true;
    }


    // Linear Probing 기법
    public String getData(String key) {
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                return this.hashTable[address].value;
            } else {
                Integer currAddress = address;
                while(this.hashTable[currAddress] != null) {
                    if(this.hashTable[currAddress].key == key) {
                        return this.hashTable[currAddress].value;
                    } else {
                        currAddress++;
                        if(currAddress >= this.hashTable.length) {
                            return null;
                        }
                    }
                }
                return null;
            }
        } else {
            return null;
        }
    }
}

// src/com.company/Main.java

package com.company;

import com.company.Hash.MyHash;

public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        mainObject.saveData("David", "01066667777");
        mainObject.saveData("Dave", "01088889999");
        System.out.println(mainObject.getData("Dave"));
    }
}

// 01088889999

참고: JAVA HashMap

• 해쉬 테이블 구조를 활용하여 구현된 JAVA Collection Framework에 속한 클래스

// src/com.company/Main.java

package com.company;

import com.company.Hash.MyHash;

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {


        HashMap<Integer, String> map1 = new HashMap<>();
        map1.put(1, "사과");
        map1.put(2, "바나나");
        map1.put(3, "포도");

        HashMap<String, String> map2 = new HashMap<>();
        map2.put("DaveLee", "01033334444");
        map2.put("Dave", "01032221111");
        map2.put("David", "01044445555");

        System.out.println(map1.get(2));
        System.out.println(map2.get("Dave"));
    }
}

// 바나나
// 01032221111

7. 시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
• Linear Probing, Chaining 기법 둘 다 동일

해쉬 테이블의 경우는 일반적인 경우를 기대하고 작성함

검색에서 해쉬 테이블의 사용 예

• 배열에 데이터를 저장하고, 검색할 때 O(n)
• 이상적인 해쉬 테이블 케이스에서 데이터를 검색할 때 O(1)