해시테이블

// string 자료형의 key에 해당하는 공간에 string 자료형의 value를 넣은 것
// 키와 값의 형태로 데이터를 저장하는 구조는 자바스크립트 object or map으로 구현가능 

class HashTable {
	table = new Array(100);
// key, item을 파라미터로 받아와 넣어줌 
	setItem = (key, value) => {};
// key를 파라미터로 받아서 table key에 맞는 value를 불러옴 
	getItem = (key) => {return '' ; };
}

// 함수 선언
function hashStringToInt(s) {
	return 3; 
}

// setItem함수 선언
// key에 어떤 값을 넣든 idx =3 
setItem = (key, value) => {
		const idx = hashStringToInt(key);
		this.table[idx] = value;
}

// 이럴 경우 인덱스가 중복되어 유실되거나, 성능 저하 => 해시 충돌
getItem = (key) => {
	const idx = hashStringToInt(key);
	return this.table[idx];
}

// key로 들어오는 문자열을 charCodeAt()으로 변환해 값을 이용함 
//charCodeAt() : 주어진 인덱스에 대한 코드를 0~65535로 바꾸어줌
// 문자를 하나씩 돌면서 숫자로 바꾸고 해시 테이블의 인덱스 계산으로 활용

function hashStringToInt(s, tableSize) {
	let hash = 17;
	for(let i =0; i<s.length; i++){
		hash = (13 * hash * s.charCodeAt(i) ) %tableSize; 
		}
return hash;
}

class HashTable {
table= new Array (80);

setItem = (key, value) => {
	const idx = hashStringToInt(key, this.table.length);
	this.table[idx] = value;
};

getItem = (key) => {
	const idx = hashStringToInt(key,this.table.length);
	return this.table[idx];
};
}

Hashing, 임의의 길이의 값을 해시함수를 사용해 고정된 크기의 값으로 변환하는 작업

해싱을 사용해 데이터를 저장하는 자료구조를 해시 테이블이라고 함

기본 자료구조인 이진탐색트리나 배열에 비해서 빠른 속도임

임의 데이터를 받아서 특정 해시값을 반환하는 함수

해시함수로 변환한 값을 색인(index)로 삼아서 key 와 데이터(value)를 저장하는 자료구조

e.g. 키 값이 100이라고 했을 때, 배열 인덱스 100에 원하는 데이터를 저장

[key] 값을 입력 받아 해시 함수로부터 반환된 Hash Code를 배열의 Index로 환산해 데이터에 접근

어떤 것과 다른 것의 관계를 모형화 할 수 있으며, key와 값을 가짐

해시 맵, 맵, 딕셔너리, 연관 배열로 알려져 있음

해시 충돌

key와 value로 이루어져있는 해쉬 테이블의 특성상, 해시 함수를 통해 각각의 다른 key가 동일한 Hash code가 되는 것을 말한다.

충돌에 의한 문제를 분리연결법과 개방주소법을 사용해 2가지로 해결하고 있다.

해시 충돌 해결

• 분리 해결법

동일한 버킷 데이터에 자료구조를 활용해 추가 메모리를 사용해 다음 데이터의 주소에 저장한다. 동일한 버킷으로 접근한다면 데이터들을 연결해서 관리해주고 있으며, 링크드리스트 데이터 구조를 활용

→ 테이블 확장이 필요없고 간단한 구현이 가능함, 쉽게 삭제 가능

→ 데이터 수가 많아짐녀, 동일한 버킷에 chaning되는 데이터가 많아져, 캐시의 효율성이 감소

• 개방 주소법

연결리스트의 추가적인 메모리 공간을 사용하지 않고, 비어있는 해시 테이블의 공간을 활용한다. (메모리 적게 차지함)

1. linear probing

현재 버킷 인덱스로부터 고정폭만큼 이동해 비어있는 버킷에 데이터를 저장

1. Quadratic Probing

해시의 저장순서 폭을 제곱으로 저장하는 방식

1. Double probing

해시된 값을 한번 더 해싱해 규칙성을 없애버리는 방식(새로운 주소를 할당해 많은 연산)

해시 테이블 구현

탐색을 최대한 줄이기 위해서, input에 대한 key값을 얻어내서 관리하는 방식

key값으 얻어서 저장할 때, 다른 문자열이더라도 같은 key값으로 들어올 수 있음