hash-table

Hashing이란?

입력 데이터를 고정된 크기의 값(해시값)으로 변환하는 기법이다. 도서관에서 책 제목을 일정한 규칙으로 서가 번호로 바꾸는 것과 비슷하다.

Hashing is a technique that generates a fixed-size output (hash value) using hash functions.

Hash function이란?

입력 키를 해시 테이블의 특정 위치(인덱스)로 변환하는 수학 공식이다. 예를 들어 전화번호 뒷두 자리를 인덱스로 쓰는 것이 간단한 해시 함수의 예시다.

A hash function creates a mapping from an input key to an index in hash table, this is done through the use of mathematical formulas known as hash functions. For example: Consider phone numbers as keys and a hash table of size 100. A simple example hash function can be to consider the last two digits of phone numbers so that we have valid array indexes as output.

좋은 해시 함수의 조건은?

키를 테이블 전체에 골고루 분산시키고, 같은 위치에 여러 키가 몰리는 충돌을 최소화해야 한다. 사물함 배정에서 특정 번호에만 사람이 몰리지 않도록 고르게 나누는 것이 좋은 해시 함수다.

A good hash function should have the following properties:

Should uniformly distribute the keys to each index of hash table.

Should minimize collisions.

Should have a low load factor (number of items in the table divided by the size of the table).

Hash Collision이란?

서로 다른 키가 해시 함수를 거쳤을 때 같은 위치(인덱스)를 가리키는 상황이다. 두 사람에게 같은 사물함 번호가 배정된 것과 같으며, 이를 해결하기 위한 별도의 충돌 해결 기법이 필요하다.

When two or more keys have the same hash value, a collision happens. To handle this collision, we use Collision Resolution Techniques.

Hash Table의 장점은?

검색, 삽입, 삭제를 평균적으로 O(1), 즉 데이터 양에 관계없이 거의 즉시 수행할 수 있다. 사전에서 단어를 찾을 때 처음부터 훑지 않고 해당 글자 섹션을 바로 펼치는 것과 비슷한 원리다.

It mainly supports search, insert and delete in O(1) time on average.

Hash Set과 Hash Map의 차이는?

Hash Set은 중복 없이 키만 저장하는 구조이고, Hash Map은 키와 값을 쌍으로 저장하는 구조다. 출석부에 이름만 적는 것이 Set이라면, 이름 옆에 전화번호까지 적는 것이 Map이다.

Hash Set: Collection of unique keys (Implemented as Set in JavaScript, HashSet in Java).

Hash Map: Collection of key value pairs with keys being unique (Implemented as Map in JavaScript, HashMap in Java).