해시테이블(HashTable)

해시테이블(HashTable)

검색하고자 하는 키 값을 해시함수를 이용하여 해시코드를 만들고 이것을 인덱스로 하는 자료구조이다.

장점

이러한 해시테이블은 속도가 빠르다(feat. O(1))는 장점을 갖고 있다.
속도가 빠른 이유는 해시테이블은 배열을 고정된 크기 만큼 만들고 해시함수로부터 만들어진 해시코드를 해당 배열의 크기로 나머지 연산하여 나눠 담기 때문이다.
즉, 해시코드 자체가 인덱스가 되므로 검색 속도가 빠르다.

주의

하지만, 주의할 점도 당연히 있다.
바로 충돌현상(collision)이다.
데이터 값이 많아지게 되면 해시코드가 같아지면서 input인 key값은 다름에도 불구하고 내부적인 key값이 같아지게 되어 충돌이 일어난다.

해결책

충돌현상을 피하기 위해 아래와 같은 해결책들이 있다.

• 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)

• Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)

• 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함

• 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

이 글에서는 체이닝을 구현해볼 것인데, 나머지 방법들은 이 블로그를 참고하기 바란다.

체이닝

private fun main() {
    val hashTable = HashTable(3)
    hashTable.put("firstName","song")
    hashTable.put("secondName","gyubin")
    hashTable.put("fullName","songgyubin")

    println(hashTable["firstName"])
    println(hashTable["secondName"])
    println(hashTable["fullName"])
    println(hashTable["song"])
}

class HashTable(val size:Int) {
    private val arr = Array<LinkedList<Node>>(size){LinkedList()}
    data class Node(val key: String, var value: String) {
        fun value(): String = value
        fun value(value: String) {
            this.value = value
        }
    }

    private fun getHashcode(key: String): Int {
        var hashcode = 0
        for (c in key) {
            hashcode += c.code
        }
        return hashcode
    }

    private fun convertToIndex(hashcode: Int): Int {
        return hashcode % arr.size
    }

    private fun searchKey(list: LinkedList<Node>, key: String): Node? {
        if (list == null) return null
        for (node in list) {
            if (node.key == key) return node
        }
        return null
    }

    fun put(key: String, value: String) {
        val hashcode = getHashcode(key)
        var index = convertToIndex(hashcode)
        var list = arr[index]
        if (list.isEmpty()) {
            list = LinkedList()
            arr[index] = list
        }
        var node = searchKey(list, key)
        if (node == null) list.addLast(Node(key, value))
        else{
            node.value(value)
        }
    }

    operator fun get(key: String): String{
        val hashcode = getHashcode(key)
        val index = convertToIndex(hashcode)
        val list = arr[index]
        val node = searchKey(list,key)
        return node?.value ?: "Not Found"
    }

}