Hash Collision(해시 충돌) Chaining(체이닝) 및 kotlin 구현

해시 충돌

hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황

Chainning (체이닝)

hashTable의 각 슬롯이 연결 리스트의 형태로 데이터를 저장하여, 동일한 출력을 값을 가지는 데이터가 들어 오더라도 같은 hash table의Idx에 저장하여 충돌을 해결한다.

새로운 데이터를 넣을때는 각 해당 슬롯의 가장 앞에 삽입한다. 그러면 항상 O(1)의 시간이 걸린다.

하지만, 검색 및 삭제는 해당 슬롯의 충돌되어 삽입된 갯수에 따라 성능이 좌우된다. 

이때, hashFunction을 C-Universal Function을 사용하면, 각 슬롯의 평균적인 연결리스트의 길이는 O(1)이라 이미 증명되어 있다.

 

class ChainingHashTable<K, V>(private var initTableSize: Int = DEFAULT_TABLE_SIZE) {

    companion object {
        private const val DEFAULT_TABLE_SIZE = 20
    }

    private var size = 0
    private var table: Array<Node<K, V>?> = Array(initTableSize) { null }

    private class Node<K, V>(val key: K, var value: V, var next: Node<K, V>? = null) {
        val hashCode = key.hashCode()

        override fun toString(): String {
            return "(key: $key value: $value)"
        }
    }

    constructor(vararg args: Pair<K, V>) : this(if (args.size > DEFAULT_TABLE_SIZE) args.size else DEFAULT_TABLE_SIZE) {

        val tableSize = if (args.size > DEFAULT_TABLE_SIZE) args.size else DEFAULT_TABLE_SIZE
        table = Array(tableSize) { null }
        args.forEach {
            put(it.first, it.second)
        }
    }

    /*
        key를 입력받아 현재 hashTable 해당하는 key값을 가진 Node가 있는지 확인합니다.
        있다면 node를 반환하고 없으면 null을 반환 합니다.
     */
    private fun findNode(key: K): Node<K, V>? {
        val idx = hashValue(key)

        var p = table[idx]

        while (p != null) {
            if (p.key == key)
                return p
            p = p.next
        }
        return p
    }

    /*
       <key, Value> 데이터를 입력받아서,
       기존에 있던 Key면 데이터를 업데이트 합니다, 없다면 새로운 데이터를 해당 idx의 Chain 가장 앞에 삽입 합니다.
    */
    fun put(key: K, value: V): K {

        val node = findNode(key)
        if (node != null && node.key == key) {
            // 값을 업데이트
            node.value = value
        } else {
            // 새로운 노드 삽입.
            table[hashValue(key)] = Node(key, value, table[hashValue(key)])
            size += 1
        }
        return key
    }

    /*
        key 값에 대응 하는 value를 리턴한다.
     */
    fun search(key: K): V? {
        val idx = hashValue(key)

        var p = table[idx]

        while (p != null) {
            if (p.key == key)
                return p.value
            p = p.next
        }
        return null
    }

    /*
        해당 key가 table에 존재한다면, key 값에 대응 하는 value를 삭제하고 key 반환.
        key가 table에 없다면, 무시한다.
     */
    fun delete(key: K) {

        val node = findNode(key) ?: return

        // 삭제할 노드의 앞선 노드를 찾는다.
        var prev = table[hashValue(key)]!!
        // 삭제할 노드가 체인의 가장 앞쪽 이라면,
        if (prev.key == node.key){
            table[hashValue(key)] = null
        }else{
            while (prev.next?.key != node.key){
                val next = prev.next ?: return
                prev = next
            }
            prev.next = node.next
            size -= 1
        }
    }

    fun hashValue(key: K) = key.hashCode() % table.size

    override fun toString(): String {
        val sb = StringBuilder()
        table.forEachIndexed { idx, chain ->
            sb.append("idx: $idx ")
            var node = chain
            while (node != null) {
                sb.append(node.toString())
                node = node.next
            }
            sb.append("\n")
        }
        return sb.toString()
    }
}