[자료구조] Hash / Hash Function / Hash Table

해시테이블 은 키(Key)와 값(Value)로 이뤄진 자료구조이다. Swift의 딕셔너리를 떠올리면 쉬운데, 내부 동작은 실제론 배열과 같다.

key를 해시함수를 통해 해시 값으로 변환하고 해시테이블에 해시 값과 대응되는 저장공간에 Value를 저장하는 것이다.

 

용어

• 키 Key : 고유한 값으로 Hash Function을 통해 HashValue로 변환한다.
• 해시 Hash : 임의의 값(Value)를 고정된 길이로 변환하는 것
• 해시함수 Hash Function : Key에 대한 산술 연산을 이용해 데이터가 저장된 공간을 가리키는 Hash Value 를 구한다.
• 해시 값 Hash Value : Key 를 Hash Function로 연산한 결과. 이를 기반으로 Hash Table에서 해당 Key에 대응 되는 Value를 찾을 수 있다.
• 값 Value : 저장 할 값
• 슬롯 Slot : 한 개의 값을 저장할 수 있는 공간

 

해시 테이블

색인에 해시 값을 사용하는 자료구조 이므로, 원하는 값에 바로 접근이 가능하다. 속도가 빠르다는 말

그러므로 추가, 삭제도 효율적으로 수행 할 수 있다.

 

일단 충분히 큰 공간을 할당받은 다음 해시 함수를 이용하여 고유 색인이 될 해시 값(hash value)을 생성한다. 그리고 이 고유 색인과 맞는 위치(Slot)에 값을 저장한다. 마지막 단계인 저장하는 부분을 코드로 해석 한다면 아래 처럼 되겠다.

해시테이블[해시 값] = 값 //해시 값은 Key가 변환된 것이다.

어디서 본 모습이다.

Swift의 Dictionary와 같지 않은가? 또 Java의 HashMap으로도 보인다.

 

그림 1

쉽게 설명하기 위해 그림 1 을 보자면 John Smith라는 키를 해시함수에 넣어서 해시로 변환하여 02가 되었다. 준비된 배열의[02] Slot에는 John Smith와 쌍을 이루는 Value가 저장되는 것이다.

 

 

 

구현

해시함수는 임의의 길이를 갖는 Key를 고정된 길이의 값으로 매핑하는 함수를 말한다. 매핑된 고정된 길이의 값 이란 바로 해시 값이다.

아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나와야 한다. 또 input에 대한 output은 항상 동일한 값이어야 한다.

만약 해시함수에게 10을 넘겨주고 3이 튀어나왔다면, 나중에 또 해시함수에 10을 넘겨 줬을 경우 3이 나와야 한다.

 

간단한 코드를 작성해보면서 해시함수가 어떤식으로 해시 값을 만들어내는지 알아보자.

해시함수를 작성하기에 앞서 저장할 데이터를 정의한다.

 

struct NameData { 
    let key: Int 
    let value: String 
} 

let keys = [10, 21, 32, 43, 54, 65, 76, 87, 98, 109] // 끝 자리가 서로 다른 열개의 key 
let values = ["홍길동", "이석훈", "강호동", "유재석", "박명수", "이효리", "하창수", "박지원", "김구", "윤봉길"] //해시테이블에 저장 될 이름정보 

var nameDatas: [NameData] = []

for index in 0 ..< 10 { 
    nameDatas.append(NameData(key: keys[index], value: values[index]))
}

해시테이블엔 이름 들을 저장할 생각이다.

key와 value를 프로퍼티로 갖고 있는 NameData를 정의하고 열개의 NameData를 nameDatas라는 배열에 넣어줬다.

뭔가 만든 느낌이지만 nameDatas에 담긴 열개의 NameData들을 해시테이블에 저장하는것이 목적이다.

 

 

이름정보가 담길 해시테이블을 만든다.

nameDatas의 count는 10이므로 각각 하나의 저장공간을 차지하게 만들려면 10개의 Slot이 필요하겠다.

nameData의 이름정보는 String타입이기 때문에 [String?] 타입으로 배열을 만들어 준다.

 

var hashTable: [String?] = [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil]// .init(repeating: nil, count: 10)

이제 해시테이블과 해시테이블에 저장 할 데이터들도 준비되었으니 해시함수를 만들 차례다.

 

 

해시 함수

10개의 NameData의 key를 가져와 해시함수를 거치면 0~9 까지의 해시값으로 변환되어야 한다. 그래야 해시테이블의 0~9 Slot에 저장 할 수 있기 때문이다.

 

10개의 key가 각각 0~9 까지의 index를 가지게 하는 방법은

key값을 준비 된 해시테이블의 요소 수로 나눈 나머지값을 사용하는 것이다.

만약 함수로 들어오는 키가 100이면 0, 123이면 3, 이후 어떤 큰 숫자가 오더라도 나머지는 10을 넘기지 않는다.

 

func getHash(_ key: Int) -> Int {
    let hashValue = key % hashTable.count // count == 10
    return hashValue 
}

nameDatas.forEach { nameData in
    print(getHash(nameData.key)) 
} 
// 출력결과 // 0 1 2 3 4 5 6 7 8 9

 

출력결과 처럼 끝자리가 서로 다른 10개의 키를 해시함수를 통해 해시값을 만들어내자, 0~9 까지의 숫자가 만들어졌다.

해시 값이 준비 되었으니 해시테이블에 저장만 하면 끝이다.

 

nameDatas.forEach { nameData in
    hashTable[getHash(nameData.key)] = nameData.value 
} 

for name in hashTable { 
    print(name) 
} 

/* 출력 결과 
Optional("홍길동")
Optional("이석훈") 
Optional("강호동") 
Optional("유재석")
Optional("박명수") 
Optional("이효리") 
Optional("하창수") 
Optional("박지원") 
Optional("김구") 
Optional("윤봉길") 
*/

해시테이블에 nameDatas의 정보들을 저장하고 출력까지 해봤다. 출력결과 순차적으로 "홍길동" 부터 마지막 이름인 "윤봉길" 까지 정상적으로 저장된걸 확인 할 수 있었다.

 

 

nameDatas의 요소가 가진 각각의 key는 서로 겹치지 않는, 그리고 해시함수를 통해 해시값으로 변환 한 후에도 고유한 값이 되었다.

그러므로 해시테이블에는 각각의 요소가 하나의 Slot에 겹치지 않게 저장이 되는 모습이다.

고유한 키 값을 지니고 있으니 저장된 데이터를 꺼내거나 삭제하는 방법도 간단하다.

 

key를 알고 있다면 해시함수를 통해 해시값을 만들고 해시테이블에서 Slot을 찾아 바로 가져오거나 삭제하면 된다.

 

for i in stride(from: 0, to: 9, by: +2) { 
    let hashValue = getHash(nameDatas[i].key)
    print(hashTable[hashValue]) 
}

/* 출력 결과
Optional("홍길동")
Optional("강호동")
Optional("박명수")
Optional("하창수") 
Optional("김구") 
*/

 

해시테이블의 0, 2, 4, 6, 8 의 인덱스에 저장된 이름들을 출력했다.

---

지금 까지 해시테이블을 사용하여 데이터를 저장하는 방법을 알아봤는데 이 해시테이블엔 치명적인 단점이 있다.

이 문제는 해시함수로 부터 생성된 hashValue가 중복되는 현상이다.

 

지금까지는 10개의 key가 각각 다른 해시 값으로 변환 되었지만,

만약 11개의 key를 해시값으로 변환하게 되면 반드시 중복되는 해시 값이 발생하게 된다.

10개의 key를 0~9 까지 중복되지 않게 만들었는데 여기에 하나의 해시값이 더 추가 된다면 0~9 의 범위 내에서 발생하기 때문이다.

 

이런 현상을 충돌이라고 한다.

0~9까지의 Slot이 모두 할당된 후 새롭게 들어오는 값이 저장공간에 이미 존재하던 값을 덮어 쓰는것은, 의도한 바가 아니고서야

원하지 않는 동작일 것이다.

 

다행이 충돌문제를 해결하기 위한 방법들이 존재한다. 그건 다음 포스팅에서

 

 

전체 코드

struct NameData { 
    let key: Int
    let value: String 
}

let keys = [10, 21, 32, 43, 54, 65, 76, 87, 98, 109] 
let values = ["홍길동", "이석훈", "강호동", "유재석", "박명수", "이효리", "하창수", "박지원", "김구", "윤봉길"] 

var nameDatas: [NameData] = []
var hashTable: [String?] = [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil] 

for index in 0 ..< 10 { 
    nameDatas.append(NameData(key: keys[index], value: values[index])) 
}

func getHash(_ key: Int) -> Int {
    let hashValue = key % hashTable.count // count == 10
    return hashValue 
}

nameDatas.forEach { nameData in 
    hashTable[getHash(nameData.key)] = nameData.value
} 

for i in stride(from: 0, to: 9, by: +2) {
    let hashValue = getHash(nameDatas[i].key)
    print(hashTable[hashValue])
}