HashTable

1.  HashTable 이란?

---

ㄴ Key & Value 로 데이터를 저장하는 자료구조

ㄴ 데이터 검색이 빠르다는 장점을 가지고 있다. 

ㄴ 내부적으로는 고유한 인덱스를 가진 버킷과 해시함수를 이용하여 값을 저장한다. (대표 버킷은 배열) 

ㄴ 예를들어, 검색하고자 하는 Key 를 입력받으면, 해시함수를 이용하여 해시코드를 반환받고, 해시코드를 버킷의 인덱스로 환산해서 데이터에 접근하는 방식의 자료구조이다. 

( * 해시를 이용하면 데이터 암호화, 간소화를 통하여 빠른비교가 가능하다. )

 

 

 

2.  HashTable 장점 

---

Func(Key)   →   HashCode    →    Index    →    Value

검색속도가 빠르다. 

ㄴ 해시함수를 통해 만든 해시코드는 정수이다. 

ㄴ 버킷공간을 고정된 크기만큼 미리 만들어놓고, 해시코드를 배열의 개수로 나머지 연산을하여 인덱스 값을 구해 배열에 나누어 담는다.( hashcode % arrary.length )

ㄴ 해시코드 자체가 버킷의 인덱스로 사용되기 때문에 검색을 하지 않아도 된다. 

ㄴ 해시코드로 바로 데이터 위치에 접근이 가능해진다. 

Key 를 버킷의 인덱스로 변경하여 Value에 접근한다.

 

 

2.  HashTable 문제점 

---

 

해시함수는 서로 다른 해시코드가 특정 인덱스에 몰리게 되는 경우 고르게 분배시키는 것이 중요하다.

 

서로 다른 키에 동일한 해시코드가 만들어져서 같은 Index를 배정받든, 

서로 다른 해시코드이지만 index 값 환산 시 같은 Index를 배정받든, 

 

하나의 Index 에 겹쳐서 저장되어야 하는 경우를 모두 충돌(Collision) 이라 한다.

 

이와 같이 해시함수 내에 알고리즘이 좋지 않을때  충돌현상이 빈번히 일어날 수 있는데, 이 경우에는 특정 인덱스에 특정 키를 찾아야 하니 하나씩 검색을 한다. 이 때 시간복잡도는  O(1) -> O(N) 으로 증가하여 성능이 떨어지므로 이를 최소화하는 것이 해시테이블에서는 중요한 이슈이다. 

 

 

 

3.  HashTable 성능

---

Key 를 버킷의 인덱스로 변환하기 때문에 검색, 저장, 삭제가 빠르다.

ㄴ 평균 시간 복잡도가 O(1), Collision 이 발생하는 경우에는 O(N) 이다.

 

 

 

4.  Java Collection Map 종류 및 특징

---

 

 

 

5. Script

---

Key 와 Value 로 이루어진 자료구조이고, 데이터 검색이 빠르다는 장점을 가지고 있다. 

내부적으로는 고유한 인덱스를 가진 버킷이라는 곳에 데이터를 저장하는데 일반적으로는 배열을 예로 많이 들고 있다. 

 

동작방식을 살펴보면, Key 값 입력 시 내부적으로 해시함수를 이용하여 정수의 해시코드를 만들어내고 해당 해시코드를 통해 인덱스 값을 구해 배열에 나누어 담는다. 이렇기에 Key 값 입력시 바로 해시코드를 통해 바로 인덱스 값을 찾을수 있기 때문에 데이터 위치에 접근이 바로 가능해진다. 

 

문제는 충돌이라는 이슈가 발생할 수 있는데 이는 서로 다른 키의 해시코드가 중첩되어 같은 인덱스를 가르키거나, 서로다른 해시코드 이지만 같은 인덱스 값을 가르키는 것을 의미한다. 이때 에는 버킷 안에 또 다른 버킷을 만들어 저장하고 이 안에서 탐색하며 데이터에 접근해야하기 때문에 O(n) 시간복잡도를 갖게 된다. 

 

그래서 해시테이블은 해시함수의 알고리즘이 얼마나 잘 구현되어있느냐에 따라 충돌이슈를 최소화 시킬 수 있다.