이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.
[TOC]
우리가 자주 사용하는 그것이 나왔습니다.
트리랑 관련이 없다는 것이 가장 큰 특징이겠네요.
해쉬 테이블은 선형적 자료구조의 특성을 가지고 있습니다. 배열에 링크드리스트를 넣은 구조죠.
자바에선 최적화를 위해 일정 크기 이상이 될 경우 검색성능을 위해 레드블랙 트리가 저장하는데 쓰이지만, 일반적인 경우는 아닙니다.
우리가 봤던 AVL 트리의 검색성능은
이럴 때 필요한 것이 테이블 자료구조 입니다. 테이블 자료구조의 검색성능은
테이블은 key와 value가 한 쌍을 이룰 때에만 테이블 자료구조라고 합니다.
그리고 value는 중복되어도 되지만, key는 중복되면 안됩니다. 우리가 O(1)의 검색성능을 얻을 수 있는 이유가 바로 여기서 나오기 때문입니다. 그리고 key가 없는 value는 존재할 수 없습니다.
테이블(Table) = 사전(Dictionary) = 맵(Map)
모두 같은 자료구조를 의미하는 단어입니다.
이 경우에 대한 예제코드는 굳이 작성하지 않겠습니다. 코드를 읽으면 대충 어떤 동작을 하겠구나라는 느낌이 오는 간단한 코드이기 때문입니다.
여기서 중요한 점은 배열은 테이블의 형태를 만족한다는 것입니다. key가 존재하지 않는 value는 있을 수 없고, key는 index로 유일합니다. 그리고, 배열의 랜덤 인덱스 조회 성능은?
여기서 테이블 자료구조는 자료구조의 시간 복잡도와 공간 복잡도간의 트레이드 오프를 잘 보여주는 자료구조라고 볼 수 있습니다.
바로, 시간 복잡도를 취한 대신 공간 복잡도가 O(n)이 된 것입니다.
그래서 우리는 해쉬를 이용해 테이블을 개선합니다.
여기서 다루는 예제 역시 충분히 이해하기 쉽다 생각해서 넘어가겠습니다.
배열의 크기를 지정하고, 데이터를 저장할 떄, 인덱스를 만들어주는 함수를 모듈로(%) 연산을 통해서 만들어주는 모습을 보실 수 있습니다. 이것이 바로 해쉬 함수라고 볼 수 있습니다. hash의 사전적의미를 검색해보시면 더 와닿으실 수 있습니다.
해쉬함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 합니다.
그런데, 이렇게 되면 만약 100개로 지정했던 범위보다 많은 데이터가 입력되면 어떻게 될까요?
아시다시피 해쉬 충돌(hash collision)이 발생합니다. 이러한 충돌은 비둘기집 원리로도 이해할 수 있습니다.
그리고, 이 문제는 배열의 크기가 문제되는 것이 아니라, 분명히 해결이 필요한 문제입니다.
충돌 해결 방법은 해시 테이블에 있어서 매우 큰 의미를 가집니다. 언어별로 Hash Table의 구현체들이 취하는 방식이 다른 것만 봐도 알 수 있습니다.
이 코드부터는 작성해나가도록 하겠습니다.
Table.java
/**
* 테이블 자료구조의 인터페이스, ADT
*
* @param <K> Key 타입에 사용될 타입 파라미터
* @param <V> Value 타입에 사용될 타입 파라미터
*/
public interface Table<K, V> {
/**
* 테이블에 key로 value를 저장합니다.
*
* @param key key 역할을 할 값
* @param value value 역할을 할 값
*/
void insert(K key, V value);
/**
* 테이블에 key값으로 저장되어있는 value를 찾습니다.
*
* @param key 검색에 사용될 key 값
* @return key값에 해당하는 value, null 가능
*/
V search(K key);
/**
* 테이블에 key값으로 저장되어있는 value를 찾아 테이블에서 제거하고, value를 반환합니다.
*
* @param key 검색에 사용될 key 값
* @return key값에 해당하는 value, null 가능
*/
V delete(K key);
}테이블 자료구조의 ADT를 표현한 인터페이스입니다. 우리가 아는 HashMap과 제네릭 선언이 똑같죠?
그리고 하는 역할이 매우 단순함을 알 수 있습니다.
Person.java
public class Person {
private final int id;
private final String name;
private final String address;
public Person(int id, String name, String address) {
this.id = id;
this.name = name;
this.address = address;
}
public void printPersonInfo() {
System.out.println(
"ID: " + this.getId() + " / 이름: " + this.getName() + " / 주소: " + this.getAddress());
}
public int getId() {
return id;
}
public String getName() {
return name;
}
public String getAddress() {
return address;
}
}Person 클래스입니다. 주민등록번호라고 ssn을 쓰셨는데 저는 그냥 id 씁니다.
그리고 불변객체로 만들었습니다. 이런 값을 나타내는 클래스는 final을 써주는게 좋은 습관인 것 같습니다.
출력하는 정보도 한 줄에 출력되도록 했습니다.
SlotStatus.java
public enum SlotStatus {
EMPTY, DELETED, INUSE
}책에 나오는 것과 동일한 의미입니다. ENUM을 활용한게 신기하네요.
Slot.java
public class Slot<K, V> {
private K key;
private V value;
private SlotStatus status;
public Slot() {
this.status = EMPTY;
}
public void insertData(K key, V value) {
this.key = key;
this.value = value;
this.status = INUSE;
}
public V deleteData() {
V returnValue = this.value;
this.key = null;
this.value = null;
this.status = DELETED;
return returnValue;
}
public V getValue() {
return this.value;
}
public K getKey() {
return this.key;
}
public SlotStatus getStatus() {
return status;
}
}Table 구현체에서 사용할 Slot 객체입니다.
예상컨데 사용은 Integer, Person으로 쓰일 것 같네요. 좀 더 객체지향적으로 설계해보려고 했는데, 느껴지실라나.. ^^;;
HashFunction.java
@FunctionalInterface
public interface HashFunction<K> {
int hashFunction(K key);
}간단한 해시함수를 선언하는 함수형 인터페이스입니다.
TableTest.java
class TableTest {
Table<Integer, Person> table;
HashFunction<Integer> hashFunction;
List<Person> persons;
@BeforeEach
void setUp() {
hashFunction = key -> key % 100;
persons = Lists.newArrayList(new Person(20202321, "디온", "경기도 광주"),
new Person(20203782, "하밀", "강남"),
new Person(20201902, "써니", "분당"),
new Person(20202457, "알렉스", "수원"),
new Person(20201390, "에버", "서울어디였는데...")
);
}
@Test
void 간단한_테이블_입력_테스트() {
table = new SimpleTable<>(hashFunction);
try {
for (Person person : persons) {
table.insert(person.getId(), person);
}
} catch (Exception e) {
fail("입력 테스트 실패");
}
}
@Test
void 간단한_테이블_탐색_테스트() {
table = new SimpleTable<>(hashFunction);
for (Person person : persons) {
table.insert(person.getId(), person);
}
Person searchedPerson;
for (Person targetPerson : persons) {
searchedPerson = table.search(targetPerson.getId());
assertThat(searchedPerson).isNotNull().isEqualToComparingFieldByField(targetPerson);
}
}
@Test
void 간단한_테이블_삭제_테스트() {
table = new SimpleTable<>(hashFunction);
for (Person person : persons) {
table.insert(person.getId(), person);
}
Person searchedPerson;
for (Person targetPerson : persons) {
searchedPerson = table.delete(targetPerson.getId());
assertThat(searchedPerson).isNotNull().isEqualToComparingFieldByField(targetPerson);
}
}
}SimpleTable.java
public class SimpleTable<K, V> implements Table<K, V> {
private final Object[] slots;
private final HashFunction<K> hashFunction;
public SimpleTable(HashFunction<K> hashFunction) {
this(100, hashFunction);
}
public SimpleTable(int initialSize, HashFunction<K> hashFunction) {
this.slots = new Object[initialSize];
this.hashFunction = hashFunction;
}
@Override
public void insert(K key, V value) {
Slot<K, V> slot = new Slot<>();
slot.insertData(key, value);
int hash = hashFunction.hashFunction(key);
this.slots[hash] = slot;
}
@Override
public V search(K key) {
Slot<K, V> slot = getSlotBy(key);
if (slot.getStatus() != SlotStatus.INUSE) {
return null;
} else {
return slot.getValue();
}
}
@Override
public V delete(K key) {
Slot<K, V> slot = getSlotBy(key);
if (slot.getStatus() != SlotStatus.INUSE) {
return null;
} else {
return slot.deleteData();
}
}
private Slot<K, V> getSlotBy(K key) {
return (Slot<K, V>) this.slots[hashFunction.hashFunction(key)];
}
}별로 어렵지 않아서 바로 구현된 클래스를 보여드립니다.
코드를 깔끔하기 위해서 제네릭으로 인해 더러워지는 부분은 함수로 추출하였습니다.
나머지는 코드만 보셔도 이해가 가시리라 생각됩니다.
충돌이 발생할 확률이 낮아야 합니다. 충돌의 해결책이 마련되어 있다 하더라도 충돌이 덜 발생해야 데이터의 저장, 삭제 및 탐색의 효율을 높일 수 있습니다. 때문에 좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'라고도 말할 수 있습니다.
"좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다."
많은 수의 데이터를 조합하여 해쉬 값을 생성했을 때, 보다 다양한 값의 생성을 기대할 수 있습니다.
좋은 해쉬 함수의 디자인 방법은 키의 특성에 따라 달라집니다. 따라서 절대적인 방법은 존재하지 않습니다.
대신 다양한 방법이 있는데 그것들 중 일부를 소개하고자 합니다.
키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 지극히 상식적인 방법입니다.
또, '비트 추출 방법'이 있는데, 비트 열에서 일부를 추출하거나 조합하는 방법입니다.
'자릿수 폴딩'은 숫자를 뭉쳐서 합친 값을 해쉬 값으로 결정하는 방법입니다.
그 밖에도 많은 해쉬 함수 디자인 방법들이 있습니다.
하지만 결국 해쉬 함수를 디자인 할 때는 키의 특성과 저장공간의 크기를 고려하는 것이 우선이라고 합니다.
테이블의 핵심주제라 할 수 있는 충돌 문제를 고민할 차례입니다.
충돌이 발생하면 빈 자리를 찾는 방법입니다.
충돌이 발생했을 떄 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 '선형 조사법'이다.
이런 선형 조사법은 충돌의 횟수가 증가함에 따라 '클러스터(cluster) 현상(특정 영역에 데이터가 집중적으로 몰리는 현상)'이 일어나는 단점이 있다.
이차 조사법은 좀 더 먼 곳의 슬롯에 데이터를 담습니다. 하지만 여기에도 문제가 있다고 합니다.
이 선형 조사법에서 우리가 Slot의 상태를 저장해둔 이유가 나옵니다. 바로, 데이터가 삭제되면 탐색시에 그 키에 해당하는 데이터가 없을 경우 그냥 검색결과가 없는 것으로 나오기 때문이죠.
따라서 삽입 탐색과정에 해당 로직이 들어가야 하겠습니다.
이차 조사법의 문제는 바로 이것입니다.
"해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다."
이중 해쉬는 이런 문제를 보완하기 위한 방법입니다. 보조 해쉬라고도 합니다.
1차 해쉬 함수: 키를 근거로 저장위치를 결정
2차 해쉬 함수: 충돌 발생시 몇 칸 뒤를 살필지 결정
소수를 해쉬 함수를 만들 때 사용하는 이유는 소수를 선택하면 클러스터 현상이 줄어들기 때문이라고 합니다.
이중 해쉬는 이상적인 충돌 해결책으로 알려져있다고 합니다.
앞서 소개한 유형들은 모두 오픈 어드레싱 방법이라고 합니다.충돌이 발생하면 다른 자리에 저장한다는 의미입니다.
반면 이번에 소개할 체이닝은 같은 자리에 저장합니다.
체이닝은 연결리스트를 사용합니다. Java는 연결 리스트 및 레드 블랙 트리를 사용합니다.
말 그대로 충돌이 발생하면 그 다음 위치에 이어서 저장하는 방식입니다.
TableTest.java
@Test
void 체이닝_테이블_입력_테스트() {
table = new ChainedHashTable<>(hashFunction);
try {
for (Person person : persons) {
table.insert(person.getId(), person);
}
} catch (Exception e) {
fail("입력 테스트 실패");
}
}
@Test
void 체이닝_테이블_탐색_테스트() {
table = new ChainedHashTable<>(hashFunction);
for (Person person : persons) {
table.insert(person.getId(), person);
}
Person searchedPerson;
for (Person targetPerson : persons) {
searchedPerson = table.search(targetPerson.getId());
assertThat(searchedPerson).isNotNull().isEqualToComparingFieldByField(targetPerson);
}
}
@Test
void 체이닝_테이블_중복_탐색_테스트() {
hashFunction = key -> 0;
table = new ChainedHashTable<>(hashFunction);
for (Person person : persons) {
table.insert(person.getId(), person);
}
Person searchedPerson;
for (Person targetPerson : persons) {
searchedPerson = table.search(targetPerson.getId());
assertThat(searchedPerson).isNotNull().isEqualToComparingFieldByField(targetPerson);
}
}
@Test
void 체이닝_테이블_삭제_테스트() {
table = new ChainedHashTable<>(hashFunction);
for (Person person : persons) {
table.insert(person.getId(), person);
}
Person searchedPerson;
for (Person targetPerson : persons) {
searchedPerson = table.delete(targetPerson.getId());
assertThat(searchedPerson).isNotNull().isEqualToComparingFieldByField(targetPerson);
}
}ChainedSlot.java
public class ChainedSlot<K, V> {
private final K key;
private final V value;
public ChainedSlot(K key, V value) {
this.key = key;
this.value = value;
}
public V getValue() {
return this.value;
}
public K getKey() {
return this.key;
}
}Status가 사라졌습니다. 왜냐하면 체이닝 방식에는 필요없기 때문입니다.
ChainedHashTable.java
public class ChainedHashTable<K, V> implements Table<K, V> {
private final List<ChainedSlot<K, V>>[] slots;
private final HashFunction<K> hashFunction;
public ChainedHashTable(HashFunction<K> hashFunction) {
this(100, hashFunction);
}
public ChainedHashTable(int slotSize, HashFunction<K> hashFunction) {
this.slots = new List[slotSize];
this.hashFunction = hashFunction;
}
@Override
public void insert(K key, V value) {
if (search(key) != null) {
System.out.println("키 중복");
return;
}
List<ChainedSlot<K, V>> slotList = this.slots[hashFunction.hashFunction(key)];
ChainedSlot<K, V> slot = new ChainedSlot<>(key, value);
if (slotList == null) {
this.slots[hashFunction.hashFunction(key)] = new DummyLinkedList<>();
slotList = this.slots[hashFunction.hashFunction(key)];
}
slotList.insert(slot);
}
@Override
public V search(K key) {
List<ChainedSlot<K, V>> slotList = this.slots[hashFunction.hashFunction(key)];
if (slotList == null || slotList.isEmpty()) {
return null;
}
for (int i = 0; i < slotList.size(); i++) {
ChainedSlot<K, V> slot = slotList.get(i);
if (key.equals(slot.getKey())) {
return slot.getValue();
}
}
return null;
}
@Override
public V delete(K key) {
List<ChainedSlot<K, V>> slotList = this.slots[hashFunction.hashFunction(key)];
if (slotList == null || slotList.isEmpty()) {
return null;
}
for (int i = 0; i < slotList.size(); i++) {
if (key.equals(slotList.get(i).getKey())) {
return slotList.remove(i).getValue();
}
}
return null;
}
}기존 구현된 링크드리스트가 차이가 많이나서 이쪽 코드를 보시는게 더 좋을 것 같습니다.
null 리턴을 드디어 반성하네요. 왠만하면 예외를 던져주는게 맞다고 생각하고 있었습니다.