해시 함수

해시함수는 문자열을 받아서 숫자를 반환 하는 함수이다.
(문자열에 대해 숫자를 할당 한다.)

해시 함수의 요건

• 일관성이 있어야 한다
  예를 들어 'apple'을 넣었을 때 '4'를 반환한다면 'apple'을 넣을 때마다 반환되는 값은 항상 '4'이어야 한다.
• 다른 단어가 들어가면 다른 숫자가 나와야 한다.
  예를 들면 어떤 단어를 넣어도 '1'만 나오면 안된다. 서로 다른 단어 에대해 모두 서로 다른 숫자가 나와야 한다.

해시테이블

해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 한다. 만약 배열이 5개의 원소만 가질수 있다면 50을 반환해서는 안된다.

해시 테이블
해시 맵, 맵, 딕셔너리, 연관 배열 이라는 이름으로도 알려져 있다.

해시 테이블은 속도가 빠르다

let book = {};

book["apple"] = 0.67;
book["milk"] = 1.49;
book["avocado"] = 1.49;

console.log(book);

// {apple: 0.67, milk: 1.49, avocado: 1.49}

해시 테이블은 key와 value를 가진다. book이라는 해시 테이블에서 상품 이름은 key가 되고, 가격은 value가 된다.

해시테이블 사용 예시

해시 테이블을 사용 하는 대표적인 예로는

• 어떤 것을 다른 것과 연관 시키고자 할때
• 무언가를 찾아보고자 할때

해시 테이블로 조회하기

전화번호부를 만든 해시 테이블

let phone_book = {};

phone_book["jenny"] = 123456;
phone_book["emergency"] = 119;

console.log(phone_book["jenny"]); // 123456

중복된 항목을 방지하기

let voted = {};

function check_voter(name) {
  if (voted[name]) {
    console.log("kick them out!");
  } else {
    voted[name] = true;
    console.log("let them vote!");
  }
}

check_voter("tom"); // let them vote!
check_voter("tom"); // kick them out!
check_voter("mike"); // let them vote!

해시 테이블을 캐시로 사용하기

캐싱이란?
정보를 다시 계산하지 않고 저장했다가 알려주는 것

캐싱의 장점

1. 웹페이지를 더 빨리 보여준다.
2. 일을 덜 할수 있다.

해시테이블의 장점

• 어떤 것과 다른 것 사이의 관계를 모형화할 수 있다.
• 중복을 막을 수 있다.
• 서버에게 작업을 시키지 않고 자료를 캐싱할 수 있다.

좋은 해시 함수란?

배열에 값을 고루 분포시키는 함수 이다!

값들이 뭉쳐있으면 충돌이 자주 발생한다.

요약

• 해시 테이블은 해시 함수와 배열을 결합해서 만든다

• 충돌은 나쁘다. 충돌을 줄이는 해시 함수가 있어야 한다.

• 해시 테이블은 빠른 탐색, 삽입, 삭제 속도를 가진다.

• 해시 테이블은 어떤항목과 다른 항목의 관계를 모형화하는데 좋다.

• 해시 테이블은 데이터를 캐싱하는 데도 사용된다.

• 해시 테이블은 중복을 잡아내는 데도 뛰어나다.

---

참고

'Hello Coding 알고리즘' 책을 공부하여 요약정리한 내용입니다.