hash

Map

• key, value 쌍들을 가진다.
• 같은 key를 가지는 쌍은 최대 한 개만 존재한다.

Hash table(hash map)

• 배열과 해시함수(hash function)를 사용하여 map을 구현한 자료구조

Hash function

• 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
• (hash table에서) 임의의 데이터를 정수로 변화하는 함수.
• 임의의 데이터(type상관없음)를 hash function에 넣으면 output으로 정수값이 hash로 나오게 된다.
  

---

Hash tables vs arrays

// array
menu = [
	{name : "coffee", price:10},
    {name : "burger", price:15},
    {name : "tea", price:5},
    {name : "pizza", price:10},
    {name : "juice", price:5},
];

이 때, pizza의 가격을 알기 위해서는 coffee 에서부터 차례로 pizza가 맞는지 확인해야하지만,

menu = {
	coffee : 10,
    burger : 15,
    tea : 5,
    pizza : 10,
    juice : 5,
}

hash table을 사용하면
menu["pizza"] 했을 때
10 이라는 결과가 나온다.
이때, pizza는 key가 되고, 10은 value 이다.