[알고리즘 - Algorithm] 해시 알고리즘

해시알고리즘에 대해 알아보자! 정보처리기사에서 해시알고리즘을 되게 얕게 배웠던 기억이 있는데, 코드에 적용해보려니 도저히 감이 오질 않아서 스터디 하게되었다.
!

해시(hash) 알고리즘의 흐름

1. 해시값을 세팅한다.
2. 해시의 key값을 해시함수를 통해 정수로 변환시킨다.
3. 변환된 정수값을 배열방 중 일치하는 인덱스에 넣는다.

이런 자료구조 형태로 구성된 테이블은 데이터를 조회할 때 효율이 엄청 좋다.
예를들어, 전국민의 성별정보가 저장되어있는 테이블에서 나의 성별을 찾고싶으면 내 이름이 나올 때 까지 조회해야 한다. 최악의 경우 모든 데이터를 조회해야하는 o(N)이 걸리게 된다.
하지만 해시로 구성된 테이블일 경우 내 이름key을 넣으면 내 이름에 해당하는 배열방을 찾을 수 있고, 그 중 내 성별을 빠르게 찾을 수 있다.

해시 (hash) ?

해시란 key와 value로 구성된 한 쌍의 자료구조이다. object나 map형태로 만들 수 있다.

var hash = {}
hash.홍길동 = '남자'

이러면 key는 '홍길동'이고 value는 '남자'인 해시 자료구조가 완성된다.

해시 함수 (hash Function)

해시 함수는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환시켜주는 함수이다. 쉽게 말해, key 값을 정수로 변환하는 함수이다. 예를들어 key값을 아스키코드로 변환하여 그 수의 합을 구하는 해시함수가 있다고 하면, 해당 함수를 거쳐 나온 값은 정수가 된다. 이 정수를 배열 방의 길이로 나눈 뒤 나머지값을 구하면 각 인덱스를 찾을 수 있을 거다.

const hashFn = (key, arr) => {
	var code = 0;
	for (k of key) {
	  code += k.charCodeAt()
	}
	return code % arr.length
}

해시 충돌 (hash Collision)

해시함수를 통해 해시테이블(배열 방)에 넣을 수 있게 되었다.
그런데, 해시 함수를 통해 변환된 'key값이 중복되는 경우가 있을 수도 있다. 예를 들어 위의 해시 함수에 전달된 key값이 홍길동과 동길홍 혹은 길동홍 등은 같은 값을 반환할 것이다. 그 외에도 같은 값을 반환하게될 경우가 충분히 있을 수 있다.

이러한 경우, 같은 인덱스를 반환하게 되면 같은 배열방 안의 저장소에 데이터들이 쌓이게 될것이다.
이러한 문제를 해결할 수 있는 방법이 있다.

체이닝 기법 (channing)

체이닝 기법은 저장소(buckets)에서 충돌이 발생하면 기존 값과 새로운 값을 linkedList를 통해 연결해주는 방법이다.
위의 이미지에서 152번 인덱스에 John Smith를 해시 함수를 통해 변환한 값과, Sandra Dee를 변환한 값이 동일한 인덱스이기 때문에, 겹치는 현상이 발생했다.
이러한 경우 두 데이터를 연결한 linkedLIst로 만들어 같이 보관하고 해당 데이터를 찾을 때에는 해당 인덱스 내에서 선형조회를 통해 찾을 수 있다.

개방 주소법 (open Addresss)

개방 주소법은 충돌이 발생했을 경우, 테이블 내의 새로운 인덱스를 탐색한 후, 비어있는 곳에 해당 값을 넣어준다. 그리고 그 공간에 원래 들어와야할 데이터가 들어올 경우 새로운 빈 공간을 찾아서 넣는 방법이다.
위의 이미지에서 마찬가지로 152번 인덱스에 John Smith를 해시 함수를 통해 변환한 값과, Sandra Dee를 변환한 값이 동일한 인덱스이기 때문에, 겹치는 현상이 발생했다.
이러한 경우 Ted Baker가 들어가야할 공간인 153번 인덱스에 Sandra Dee가 들어갔고, Ted Bakersms 154번 인덱스에 위치해있다.

TIL
지금까지 코딩을 하면서 key값이 string 구조로 찾고자하는 경우가 분명이 있었다. jsonArray로 구성된 데이터를 핸들링하는 일이 많았는데 그럴 때마다 순회함수를 돌리면서 퍼포먼스가 좋지 않은 코드를 작성했던 것 같다. 이제 해시 테이블 구조를 활용한 문제도 풀어보면서 문제해결능력을 길러 추후에 작성될 코드에 대입할 수 있도록 해야겠다.