옆집 스위프트: 1-7) 데이터 구조 - 해시 테이블과 해시 함수(Hash)

오늘은 딕셔너리 타입 해시 테이블에 대해서!

 

7. 해시 테이블과 해시 함수(Hash)

• 해시함수: 입력(또는 키)을 받아 고정 크기의 문자 문자열을 생성하는 수학적 알고리즘으로, 이는 해시된 값을 나타낸다. 해시 함수의 주요 목표는 충돌을 최소화하기위해 사용 가능한 배열 위치에 키를 효율적으로 분산시키는 것이다.
  • 분할 메서드: 키를 해시 테이블의 크기(m)로 나누고 나머지를 해시 값으로 사용한다. 해시 테이블의 크기가 소수일 때 잘 작동한다. hashValue = key % m
  • 곱셈 메서드: 일정한 배수(A)를 키와 곱하고, 결과의 소수 부분을 해시 값으로 사용한다. 곱셈 메서드는 분할 메서드보다 키의 더 균일한 분포를 제공한다. hashValue = floor(m * (key * A % 1))
  • 폴딩 메서드: 키를 여러 부분(숫자 또는 문자)으로 나눈 다음, 덧셈 또는 XOR과 같은 산술 연산을 사용하여 이러한 부분을 결합한다. 최종 결과는 해시 값으로 사용된다.
  • 다항 롤링 해시 함수: 문자열을 해싱하는데 특히 유용하다. 문자열의 각 문자를 다항식의 계수로 취급하고, 특정 값에서 다항식을 평가한다. 평가 결과가 해시 값으로 사용된다.

// 스위프트의 해시 테이블
// 스위프트는 해시 테이블을 사용하여 내장 딕셔너리(Dictionary) 타입을 제공한다.

// 해시 테이블 생성
var hashTable = [Int:String]()

// 데이터 삽입
hashTable[1] = "HashBrown"
hashTable[2] = "HashGreen"
hashTable[3] = "HashOrange"

// 데이터 검색(비어있을 수 있으므로 옵셔널로 출력된다.)
print(hashTable[2]) //Optional("HashGreen")

// 데이터 제거
hashTable removeValue(forKey: 2)