Hash Table 자료구조 정리

 

언어마다 'Hash Table' 이라는 자료 구조를 제공하는데

swift에서는 'Dictionary'라는 해시 테이블 자료구조를 사용할 수 있다.

해시 테이블이란 key-value 쌍을 갖는 리스트이며, 빠른 읽기가 가능하다.

무슨 말이냐?

 

 

예를 들어

메뉴와 가격이 적혀있는 메뉴판이 하나 있다.

( 아아 = 2500, 아바라 = 3500, 아이스초코 = 5000, 얼음물 = 10000, 레몬에이드 = 2000 )

레몬에이드의 가격을 얻고싶다면?

 

배열로 생성하고, 검색할 경우 Linear Search를 사용한다.

한 배열 내에 존재하기 때문에 비슷한 주소값을 갖는다 하더라도 인덱스를 하나씩 뒤져봐야 하므로 O(N)만큼의 시간복잡도를 갖게 된다.

 

하지만 이 값이 해시테이블에 들어있다면?

'레몬에이드'(key)만 가지고 해당 위치에 바로 접근할 수 있게 되어 O(1)을 갖게 된다.

사실 그냥 O(1)도 아니고 단 한단계만 필요함

물론 해시테이블을 사용한다고 해서 무조건 O(1)을 갖는 것은 아니다.

해시 충돌이 일어나는 경우에 추가적인 단계가 필요하게 되는데 아래 어딘가에 나올 것임

 

 

해시테이블이 빠를 수 있는 이유는 해시 함수에 있다.

......ㅎㅎ

'Hash'의 의미가..................따로 있는 건 아니고

어떤 데이터를 받아서 특정한 크기의 데이터로 매핑해주는 함수를 뜻한다.

어떤 데이터를 받았을 때 항상 동일한 값이 나오도록 함수를 만들어주면 되는데,

swift나 최근에 나온 언어들은 기본 라이브러리에 해시함수가 포함되어 있기 때문에

굳이 따로 구현할 필요 없이 바로 해시값을 추출해서 사용한다.

포함되어 있지 않은 경우에도 본인이 구현하는 것보다는 알려져있는 유명한 해시 알고리즘을 가져와서 사용하면 되는데

MD, SHA 등이 있다.

 

 

---

해시 테이블을 사용하는 과정은 다음과 같다.

 

1. key 값을 해싱함 : 키에 해시함수를 적용시켜 특정 값을 얻음

2. 얻은 값을 index로 하여 셀의 해당 인덱스에 value를 저장

3. 다음 key-value 값들에 대해 반복..

-> 해시테이블 완성

4. 검색하고자 하는 key 값을 동일한 해시함수로 해싱함

5. 해싱한 값을 index로 하여 해시테이블에서 바로 뽑아옴

---

 

이런 과정에서 해시 충돌(Collision)이 일어날 수 있는데

서로 다른 key를 해싱한 값이 동일할 때 발생한다.

해시 함수를 아무리 정교하게 만들었다고 하더라도 서로 다른 key에 대해 동일한 값을 얻는 경우가 있을 수 있다.

이러한 충돌을 해결하는 방법에는 개별 체이닝(Separate Chaining), 오픈 어드레싱(Open Addressing) 등이 있다.

 

 

예시와 함께 정리해보려 한다.

---

박지성 : 31

손흥민 : 7

모하메드살라 : 11

리오넬메시 : 10

웨인루니 : 10

---

축구선수의 이름과 등번호를 key-value pair로 해시테이블을 만들어보자

해시함수는 선수의 이름 글자수를 반환하는 것으로 가정해보려 한다.

박지성과 손흥민을 해시함수에 넣으면(...) 3의 해시값을 얻게 된다.

이는 해시 충돌이 발생하는 것을 의미하는데, 두 가지 방법으로 해결하는 것을 살펴보자.

 

+) value가 같은 것은 아~~무~~~런~~~~~~~ 의미가 없음

 

 

해싱결과 - 개별 체이닝 (Separate Chaining) 예시

Key	해시함수	해시테이블 (index)
박지성	글	0
손흥민	자	1
모하메드살라	수	2
리오넬메시	세	3	박지성, 31	손흥민, 7	**충돌해결
웨인루니	기	4	10
	얍	5	10
		6	11

 

충돌이 발생하는 경우, 해당 인덱스의 공간에 배열을 만들어버리고 key-value pair를 저장함

이후 박지성 혹은 손흥민을 검색하려고 할 때

해싱된 값 3이 있는 곳에서 Linear search 수행함.

--> 이런 경우 O(1)이 아니게 되는것임

그래도 쌩으로 선형탐색하는것보단 훨~씬 빠름

 

가장 전통적인 해시충돌 해결방식임

 

 

해싱결과 - 오픈 어드레싱 (Open Addressing) 예시

Key	해시함수	해시테이블 (index)
박지성	글	0
손흥민	자	1
모하메드살라	수	2	7	**충돌해결
리오넬메시	세	3	31
웨인루니	기	4	10
	ㅇㅇ	5	10
		6	11

 

충돌이 발생하는 경우, 테이블 공간을 뒤져서 근처에 있는 빈 공간에 value를 넣음

해시값과 일치하는 곳에 저장된다는 보장이 없긴 함

구현방법이 간단하고 성능이 좋은 편이라고 함.

 

 

 

 

 

어쨌거나..

해시테이블을 직접 구현해서 쓸 것은 아니기 때문에 대략적인 개념만 정리해보았다.

 

이 해시테이블의 개념을 이용하여 빠른 배열을 만들 수도 있다.

key - 원하는 data

value - True

값을 주고 검색하면 개빠르게 검색 가능!

이 때 key에 해당하는 값이 있는지만 검색하려는 것이기 때문에 value의 값은 중요하지 않고 통일되기만 하면 됨

 

 

그렇다면..

이 해시테이블 자료구조의 예제를 살펴보자

스위프트로..!

 

 

1. [1,2,3,4,5]과 [0,2,4,6,8]의 교집합을 O(N)으로 구할 것.

func getCommon(arr1:[Int], arr2:[Int]) -> [Int] {
	var intersection = [Int]()
	var hashTable : [Int:Bool] = [:]
	for i in 0..<arr1.count {
		hashTable[arr1[i]] = true
	}

	for j in 0..<arr2.count {
		if hashTable[arr2[j]] != nil {
			intersection.append(arr2[j])
		}
	}

	return intersection
}

let arr1 = [1,2,3,4,5]
let arr2 = [0,2,4,6,8]

getCommon(arr1: arr1, arr2: arr2)

 

 

2. 문자열 배열을 받고, 중복되는 값을 출력, O(N)이어야 함

func returnDuplicate(arr: [Character]) {
	var hashTable: [Character:Bool] = [:]

	for i in arr {
		if hashTable[i] != nil {
			print(i)
		} else {
			hashTable[i] = true
		}
	}
}

let arr : [Character] = ["a","b","c","d","a","e","c","a"]
returnDuplicate(arr: arr)

 

 

3. 26개의 알파벳 a-z 중 한 글자를 제외하고 모두 포함하는 문자열을 받고, 빠진 문자를 출력

O(N)이어야 함

 

let myString = "ab cef ghijk lmnopqr st uvwx yz" // d 빠짐
myString.filter{$0 != " "}

func missingAlphabet(str: String) {
	let alphabet = "abcdefghijklmnopqrstuvwxyz"
	var hashTable : [Character:Bool] = [:]

	for j in str {
		hashTable[j] = true
	}

	for k in alphabet {
		if hashTable[k] == nil {
			print(k)
		}
	}

}

missingAlphabet(str: myString.filter{$0 != " "})

 

 

 

4. 입력받은 문자열에서 한 번만 등장하는 문자 중 먼저 나오는 문자만!!!! 출력, O(N)이어야 함

 

let myString = "leehyolee" // h만 출력되어야 함

firstSolo(str: myString)

func firstSolo(str: String) {
	var hashTable : [Character:Int] = [:]
	
	for i in str {
		if hashTable[i] == nil {
			hashTable[i] = 1
		} else {
			hashTable[i]! += 1
		}
	}
	
	for j in str {
		if hashTable[j] == 1 {
			print(j)
			break // h'만' 출력되어야 하기 때문에 멈춰줌
		}
	}
}

 

 

끝