해시(Hash)

고기와 감자를 잘게 다져 요리한 해쉬브라운에서 유래되었다. 입력받은 수를 잘게 다져 입력한 것과 비슷하여 해시라는 이름을 가지게 되었다.

데이터를 다루는 기법 중 하나로 검색과 저장이 빠르게 진행을 할 수 있는 선형자료 알고리즘이다.
데이터를 검색할 때 사용할 key와 실제 데이터의 값이 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 떄문에 검색과 저장의 평균적인 시간 복잡도가 O(1)과 같아진다.

해시 테이블

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조이며 삽입은 O(1), 키를 알고 있으면 삭제,탐색도 O(1)로 수행이 된다.

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수, (지정된 방법은 없고 자유롭게 구현 가능)
ex)

• 입력받은 각 문자열을 각 문자열의 아스키코드를 더하는 값 등
• 이름, 나이, 성별 별로 나뉠 때

해시의 문제점 (충돌)

충돌 : 해시 함수의 결과가 동일하여 겹칠 때 생기는 문제
같은 key를 가지고 있지만 다른 값을 가지고 있을 때 발생하는 현상

선형 탐사법

• 충돌이 발생하면 옆으로 한 칸씩 이동한다.
• 테이블의 크기가 늘어나면 늘어날 수록 연산속도가 느려진다는 단점을 가지고 있다.
  

제곱 탐사법

• 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
• 테이블의 크기가 늘어나면 늘어날 수록 연산속도가 느려진다는 단점을 가지고 있다.
• 사용되지 않는 데이터 즉, 불필요한 데이터들이 생겨 날 수가 있다.
• 처음 충돌한 위치가 같으면 다음 충돌 위치에서도 반복적오르 충돌이 일어날 수가 있다.
  (ex: 충돌한 곳의 key가 0이나 1일 경우 제곱을 해도 같은 자리에서만 맴돈다.)
  

이중 해싱

• 충돌이 발생하면 다른 해시 함수를 이용한다.
• 충돌이 발생하면 2번째 해시 함수를 이용해서 새로운 인덱스를 만들고, 충돌하지 않을 때까지 인덱스를 계속해서 만들어서 저장한다.
  

분리 연결법

• 충돌이 발생할 경우 연결 리스트로 사용해서 리스트에 값을 추가한다.
• 최악의 경우에는 하나의 리스트에 무한정으로 늘어 날 수가 있다.
  

어디에 사용이 되는가

예를 들어 출석부 처럼 번호와 이름이 한 쌍으로 이뤄져있는 경우 유리하다. 번호는 키, 이름은 value값으로 지정 해주어 탐색이나, 삭제 기능을 쉽고 간편하게 사용할 수 있는 장점이 있다.

해쉬 테이블 코드

객체

const table = {}
table['key'] = 100;
table['key2'] = 'hello';
table['key3'] = 1
delete table['key'] ;
// table = { 'key2' : 'hello', 'key3' : 1}

Map Object

• 객체는 정수가 아닐 경우 모두 문자열로 바꾸기 때문에, Map을 통해서 다양한 타입으로 넣어 줄 수 있는 장점이 있다.
• set, get, delete, keys() ... 다양한 메소드를 통해서 쉽게 데이터를 입출력 해 줄수가 있다.

const table = new Map()
table.set ("key", 100);
table.set ("key2", 'hello'); 
table.set ('obj', {"a": 3}); //Map(3) {'key' => 100, 'key2' => 'hello', 'obj' => {'a': 3}}
table.get ('obj') // {'a' : 3}
table.keys() // {'key', 'key2', 'obj'}
table.delete('obj') Map(2) {'key' => 100, 'key2' => 'hello'}
table.clear() {}

Set Object

• 키와 값이 동일하게 저장되는 방법을 채택하고 있고, 중복된 내용을 전부 제거할 때 유용하게 사용할 수가 있다.

const table = new Set()
table.add ("key");
table.add ("key2"); 
table.has('key') //true
table.delete('key') // ['key']