[자료구조] 해시테이블(HashTable)이란 무엇인가? +HashMap

1. HashTable란 도대체 무엇?

 

해시테이블은 해시함수를 거쳐 만들어진 key와 해시함수를 거치기 전 데이터인 value를 묶어 함께 저장하는 자료구조이다.

(여기서 key값은 value값에 대한 색인, 주소 역할을 한다.)

 

 

 

*용어 정리

*Hash 함수 : 일정 값이 input인풋으로 들어가면 고정된 길이의 값을 output으로 반환해주는 함수

*Hashing : 특정 value가 hash함수를 거쳐 key값을 반환하고 key:value형태로 해쉬 테이블에 저장되는 모든 과정

 

 

 

 

2. 특징

 

"리소스 < 속도"

 

해시 테이블을 만들기 위해서는 key값이라는 것을 기억할 새로운 메모리 공간이 필요하기 때문에 기존 방법보다 리소스가 많이 든다.

하지만 key값으로 바로 value값을 찾을 수 있기 때문에 찾는 속도는 O(1)이다.

 

 

    #왜 시간 복잡도가 O(1)인가?

예를 들어, "알고" : "마스터" 라는 쌍으로 저장을 한다고 가정해봅시다.
내부적으로 해쉬 테이블은 key값인 "알고" 를 해시함수에 넣어 특정한 정수값을 만듭니다.
이후 이 정수값을 활용하여 data[정수값] = "마스터" 형식으로 배열에 담는 것입니다.

그 결과 이후 "알고" 라는 키워드로 검색하면 똑같이 해시함수가 동작해 정수값을 반환해주고 
그 정수값을 index로 해서 값을 바로 찾아올 수 있는 것입니다.

 

 

 

"해시 충돌의 문제"

 

서로 다른 value에 대해서 해시 함수로 처리한 결과값이 같을 수 있다.

이 경우 같은 공간에 한 개 이상의 value가 들어가려고 하기 때문에 문제가 된다.

 

 

  *해결 방법

 

1. chaining : 충돌이 일어나면 기존값과 새로운 값을 연결리스트를 이용해 연결한다.

 

2. open addressing : 충돌이 일어나면 비어있는 다른 버켓에 저장한다.

 

 

 

 

3. 코드로 구현하기

 

연결리스트로 chaining이 적용된 예시입니다.

import java.util.*

fun main(){

    val hashTable = HashTable(3)
    hashTable.put("알고", "마스")

    print(hashTable.get("알고"))

}

class HashTable(val size : Int){
    var data = MutableList<LinkedList<Node>>(size){
        LinkedList<Node>()
    }

    class Node(val key: String, var value: String){

    }

    //해쉬 함수
    fun getHashCode(key: String) : Int{
        var hashCode = 0
        for (c in key.toCharArray()){
            hashCode += c.toInt()
        }
        return hashCode
    }

    //해쉬코드를 정수값으로 변형(size에 맞게 넣어야 하기 때문)
    fun convertToIndex(hashCode: Int): Int{
        return hashCode % size-1
    }

    //링크드리스트에서 해당 key값 찾기
    fun searchKey(list : LinkedList<Node>, key: String) : Node? {
        if(list == null) null
        for(node in list){
            if(node.key.equals(key)){
                return node
            }
        }
        return null
    }


    fun put(key: String, value: String){
        val hashCode = getHashCode(key)
        val index = convertToIndex(hashCode)
        var list: LinkedList<Node> = data[index]

        //해당 배열 방 링크드리스트에 key와 같은 값이 있는지 확인
        val node = searchKey(list, key)

        //해당 key값이 없다면 추가, 있다면 변경
        if(node == null){
            list.addLast(Node(key, value))
        } else {
            node.value = value
        }
    }
    

    fun get(key: String) : String{
        val hashcode = getHashCode(key)
        val index = convertToIndex(hashcode)
        val list = data[index]
        val node = searchKey(list, key)
        return node?.value ?: "not found"
    }


}

*참고 : www.youtube.com/watch?v=Vi0hauJemxA

 

 

 

+ 자바에서  HashTable vs HashMap

 

- HashMap은 보조 해시 함수를 사용해서 해시 충돌이 덜 발생한다.

 

- HashMap은 동기화를 지원하지 않는다(그래서 동시화를 지원하는 HashTable이 좀 더 느리다고 한다.)