해시테이블이란? ( What is a hash table?)

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료 구조이다.

해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다.

 

해시테이블의 시간 복잡도 :  O(1) but 데이터 충돌이 발생한 경우 Chaning에 연결된 리스트까지 검색해야하므로 O(N) 까지 시가나복잡도가 증가할 수 있다.

 

데이터 충돌 시 해결법

1. Linear Probing

index 뒤에 있는 버킷 중 빈 버킷을 찾아서 데이터를 넣는 방식

2. Chaning

자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. linked List방식

3. Resize Hash Table

버킷 개수가 일정 개수 이상이 넘으면  두 배씩 늘려가는 것을 의미합니다.

 

Java의 HashMap과 HashTable 차이

1. 동기화 지원 여부의 차이가 있다.

해쉬 테이블의 put은 synchronized 키워드가 붙어있다. 그러기 때문에 병렬 프로그래밍을 할 때 동기화를 지원해준다는 것을 의미한다. -> 해당 함수를 처리하는 시간이 조금 지연될 수 있다.

 

2. HashMap 에서는 null을 key 나 value로 저장할 수 있다. HashTable은 그럴 수 없다.

 

3. 따라서 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용하고 병렬처리를 하지 않거나 동기화를 고려하지 않는 상황이면 HashMap을 사용하면 된다.

 

 

---

A hash table is a type of data structure that stores key-value pairs.

 

Components of a hash table

1. Hash function

the hash function determines the index of our key-value pair. Choosing an efficient hash function is a crucial part of creating a good hash table. Another property of a good hash function is that is that it avoids producing the same hash for different keys.

 

2. Array

The array holds all the key-value entries in the table. The size of the array should be set according to the ammount of data expented.

 

Collisions in hash table & resolutions

1. Linear probing

If a pair is hashed to a slot which is already occupied, it searches linearly for the next free slot in the table.

2. Chaining

All keys mapping to the same index will be stored as linked list nodes at that index.

3. Resizing the hash table

A hash table with a threshold of 0.6 would resize when 60% of the space is occupied. As a convention, the size of the hashtable is doubled.

 

Operation	Average	Worst
Search	O(1)	O(n) When data collisions,  You should search chanining data.
Insert	O(1)	O(n)
Deletion	O(1)	O(n)
Space	O(n)	O(n)

 

Differences between HashMap and HashTable in Java

HashMap and HashTable store key/value pairs in a hash table. 

1. HashMap is non synchronized. it is means not-thread safe and can't be shared between many threads.

2. HashMap allows one null key and multiple null values whereas Hashtable doesn't allow any null key or value.

3. HashMap is generally preferred over HashTable if thread synchronization is not needed

 

 

참고사이트(Reference site)

mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

www.educative.io/edpresso/what-is-a-hash-table

What is a hash table?

www.geeksforgeeks.org/differences-between-hashmap-and-hashtable-in-java/

Differences between HashMap and HashTable in Java - GeeksforGeeks