알고리즘 - ( 해시테이블 )

해시테이블 정의

쌍으로 이루어진 값들의 리스트이다.

해시테이블 코드 예시

menu = {
	"french fries":0.75,
	"hamburger":2.5,
	"hotdog":1.5,
	"soda":0.6,
}

첫번째 항목 : 키(key) - 두번째 항목 : 값(value)

menu["french fries"] → 0.75

해시테이블에서 룩업은 딱 한단계만 걸리므로 효율성이 O(1)이다.

*룩업: 가져오다(select)

문자를 가져와 숫자로 변환하는 과정 = 해싱
글자를 특정 숫자로 변환하는 데 사용한 코드 = 해시함수

A:1 , B:2 , C:3 , D:4
라고 가정했을 때,
해시함수를 문자에 해당하는 모든 수를 곱해서 반환 이라고 치자!
그럼, ABD → 1x2x4 = 8
항상 8이 나오게 된다. (곱셈 해시함수를 쓰면 DAB 역시 BAD 처럼 8로 변환되기 떄문에 유의해야함. (일단 넘어감)

---

유의어 사전 (해시테이블 실제 예시)

<thesaurus 해시테이블>

배열과 유사하게 해시테이블은 내부적으로 데이터를 한줄로 이뤄진 셀 묶음에 저장한다. (각 셀마다 주소가 있다.)
(곱셈 해시함수로는 인덱스 0에 아무 값도 저장되지 않으므로 인덱스 0은 제외했다.)

첫번째 항목에 해시테이블 추가

thesaurus[”bad”] = “evil”

{”bad”:”evil”}

bad → 2x1x4 = 8

키 bad는 8로 해싱되므로 컴퓨터는 값evil을 다음과 같이 셀 8에 넣는다.

2번째 항목에 해시테이블 추가

thesaurus[”cab”] = “taxi”

{”cab”:”taxi”}

cab → 3x1x2 = 6

키 cab는 6로 해싱되므로 컴퓨터는 값taxi을 다음과 같이 셀 6에 넣는다.

⇒ 해시테이블에서 항목을 룩업할 때는 키를 사용해 연관된 값을 찾는다.

키 “bad”의 값을 룩업 하고 싶다면,,

thesaurus[”bad”] (컴퓨터는 2단계를 실행한다.)

1. 컴퓨터는 룩업하고 있는 키를 해싱한다. (BAD = 2x1x4 = 8)
2. 결과가 8이므로 셀 8을 찾아가서 저장된 값을 반환한다. 여기서 문자열은 “evil”이다.

이렇게 해시테이블을 사용하게 되면 실제 항목을 키로 사용해서 해시테이블 룩업을 O(1)만에 할 수 있다.

단방향(one-direction) 룩업

• 해시테이블에서 한단계만에 값을 찾는 기능은 그 값의 키를 알 때만 가능하다.
• 키를 모른 채 값을 찾으려면 해시테이블 내 모든 키/값 쌍을 검색하는 수밖에 없고 이는 O(N)이다.
• 값을 이용해 연관된 키를 찾을 때는 해시테이블의 빠른 룩업 기능을 활용하지 못한다.
  • 키가 값의 위치를 결정하기 때문이다.
  • 한 방향, 즉, 키를 사용해 값을 찾는 식으로만 동작한다.
• 각 키는 해시테이블에 딱 하나만 존재할 수 있으나, 값은 여러 인스턴스가 존재할 수 있다.

---

해시테이블의 문제 (충돌해결)

아까 위에서 썼던 thesaurus 해시테이블을 가져온다.

thesaurus[”dab”] = “pat”

dab → 4x1x2 = 8

이미 채워진 셀에 데이터를 추가하는 것은 충돌이다.

충돌 해결법
→ 분리 연결법 : 충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법

1. 컴퓨터는 키를 해싱한다. DAB = 4x1x2 = 8
2. 셀 8을 룩업한다. 컴퓨터는 셀 8이 하나의 값이 아닌 배열들의 배열을 포함하고 있음을 알게된다.
3. 각 하위 배열의 인덱스 0을 찾아보며 룩업하고 있는 단어인 (”dab”) 을 찾을 때까지 배열을 차례대로 검색한다. 일치하는 하위 배열의 인덱스 1에 있는 값을 반환한다.

📌 but, 컴퓨터가 확인 중인 셀이 배열을 참조할 경우, 다수의 값이 들어있는 배열을 선형검색해야하므로 검색에 단계가 더 걸린다.
⇒ 따라서, 최악의 경우 해시테이블 룩업 성능은 사실상 O(N)이다.

그럼, 어떻게 해야 설정해야 해시테이블의 충돌을 가능한 적게 일어나게 할 수 있을까? (대부분의 프로그래밍 언어에서 해시테이블을 구현하고 이를 대신 처리한다. → 거의 O(1)에 가깝게 구현)

효율적인 해시테이블 만들기

📌 해시테이블의 효율성 3가지 요인

• 해시테이블에 얼마나 많은 데이터를 저장하는가
• 해시테이블에서 얼마나 많은 셀을 쓸 수 있는가 (적은 셀에 많은 데이터를 저장하면 충돌이 많아지니까,,)
• 어떤 해시함수를 사용하는가

좋은 해시함수란,,

• 사용 가능한 모든 셀에 데이터를 분산시키는 함수(데이터를 넓게 퍼뜨릴수록 충돌이 적다)
• 해시테이블에 많은 셀은 둔다. (충돌은 확실히 피할 수 있지만, 메모리를 많이 잡아먹으므로, 균형이 맞아야함.)

📌 충돌 조정
좋은 해시테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.
ex. 해시테이블에 저장된 데이터가 7개라면 → 셀은 10개
데이터 14개라면 → 셀 20개
데이터와 셀 간 이러한 비율 = 부하율

해시테이블로 데이터 조직

해시테이블은 쌍으로 된 데이터와 자연스럽게 들어 맞아서 심지어 어떤 경우에는 해시 테이블로 조건부 로직을 간소화 할 수 있다!

• 아래 조건부 로직과 해시테이블 로직을 비교해보자.

// 조건부 로직
function status_code_meaning(number){
	if(number === 200){
		return "OK"
	}else if(number === 301){
		return "Moved permanently"
	}else if(number === 401){
		return "Unauthorized"
	}else if(number === 404){
		return "Not Found"
	}else{
		return "Intenal Server Error"
	}
}

//해시테이블 이용
const STATUS_CODES = {
	"200":"OK",
	"301":"Moved permanently",
	"401":"Unauthorized",
	"404":"Not Found",
	"500":"Intenal Server Error"
}

function status_code_meaning(number){
	return STATUS_CODES[number]
}

해시테이블로 구현함으로써, 굉장히 로직들을 단순화 할 수 있다.

해시테이블로 속도 올리기

해시테이블은 쌍으로 된 데이터와 완벽하게 들어 맞지만, 쌍이 아닌 데이터라도 코드를 빠르게 만들때 쓰일 수 있다.

array=[61,30,91,11,54,38,72]

→ 정렬이 되어 있지 않으므로, 선형검색으로 N단계가 걸린다.

하지만, 해시테이블로 변경시,

hash_table={
	61:true,
	30:true,
	91:true,
	11:true,
	54:true,
	38:true,
	72:true,
}

→ hash_table [72] → 1단계만에 숫자 72를 룩업할 수 있다.

배열을 해시테이블로 변환하면 O(N) → O(1)로 시간복잡도가 바뀌어버린다.

⇒ 이런 방식을 “해시테이블을 인덱스로 사용하기”

---

• 배열의 부분 집합

한 배열이 다른 배열의 부분집합인지 알아내는 문제

[”a”, ”b”, ”c”, ”d”, ”e”, ”f”][ ”b”, ”c”, ”d”, “h”]

// 중첩루프
function isSubset(array1, array2){
	let largerArray;
	let smallerArray;
	
	// 어느 배열이 더 작은지 알아낸다.
	if(array1.length > array2.length){
		largerArray = array1;
		smallerArray = array2;
	}else{
		largerArray = array2;
		smallerArray = array1;
	}
	
	for(let i = 0; i < smallerArray.length; i++){
	
		// 작은 배열의 현재값이 우선은
		// 큰 배열에 없다고 임시로 가정
		let foundMatch = false;
		
		// 작은 배열의 각 값에 대해
		// 큰 배열을 순회한다.
		for(let j=0; j < largerArray.length; j++){
		
			// 두 값이 같으면 작은 배열의 현재값이 
			// 큰 배열에 있다는 뜻
			if(smallerArray[i] === largerArray[j]){
				foundMatch = true;
				break;
			}
		}
		
		// 작은 배열의 현재값이 큰 배열에 없으면
		// false 반환
		if(foundMatch === false) return false
	}
	
	// 루프 끝에 도달하면
	// 작은 배열의 모든 값이 큰 배열에 있다는 뜻
	return true
}

알고리즘 효율성 - 첫번째 배열의 항목 수에 두번째 배열의 항목 수를 곱한 만큼 실행

→ O(N * M)

해시테이블 연습문제

function 교집합(array1,array2){
	let largerArray;
	let smallerArray;
	let hashTable = {};
	let newArray = [];
	
	// 어느 배열이 더 작은지 알아낸다.
	if(array1.length > array2.length){
		largerArray = array1;
		smallerArray = array2;
	}else{
		largerArray = array2;
		smallerArray = array1;
	}
	
		//largerArray의 모든 항목을 hashTable에 저장한다.
	for(const value of largerArray){
		hashTable[value] = true;
	}
	
	for(const value of smallerArray){
		if(hashTable[value]){
			newArray.push(value);
		}
	}
	
	return newArray;
}

---

function duplicate(array){
	let hashTable = {};

	for(const value of array){
		if(hashTable[value]){
			return value;
		}
		hashTable[value] = true;
	}
	return "중복없음"
}

---

// 작은걸 해시테이블로 만들어야한다!

function 빠진문자열(text){	
	let hashTable = {};
	for(const value of text){
		hashTable[value] = true;
	}
	
	for(const value of "abcdefghijklmnopqrstuvwxyz"){
		if(!hashTable[value]) return value;
	}
}

---

function notDuplicate(string){
	let hashTable = {};

	for(let i =0; i < string.length; i++){
		if(hashTable[string[i]]){
			hashTable[string[i]]++; //1씩을 더한다.
		}else{
		  hashTable[string[i]] = 1; //처음 나왔더라면 1로 초기화
		}
	}
	
	for(let j=0; j < string.length; j++){
		if(hashTable[string[j]]===1){
			return string[j];
		}
	}
}