목차
자료구조
해시 충돌
해시 함수 예시
public int hash(String key) {
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
}
return asciiSum % size;
}
Java
복사
위 해시함수를 사용하면 minwoo와 oownim 의 해시값이 같아진다.
minwoo가 들어있는 공간에 oownim이 또 들어가려고하는 충돌이 발생한다.
이와 같이 해시 값이 겹쳐 발생하는 문제를 해시 충돌이라고 한다.
해결방법
1. 공간안에 또 다른 공간
내가 들어갈 자리에 누군가 있다면 리스트, 배열로 그 공간을 함께 사용한다.
public void insert(String key, Integer value) {
int hashCode = hash(key);
if (this.table[hashCode] == null) { // 들어갈 공간에 List가 초기화 되어있지 않다면
this.table[hashCode] = new ArrayList<>(); // List 초기화
}
this.table[hashCode].add(new Node(key, value)); // Node 객체를 생성해 List에 추가
}
Java
복사
2. 자리가 없으면 다른 빈 공간을 찾는다.
중복이 발생하면 다른 빈 칸을 찾아 넣는다.
Node? List<Node>[] ???
Node
public class HashTable {
private int size = 10000;
private List<Node>[] table = new List[size];
class Node {
private String key;
private Integer value;
public Node(String key, Integer value) {
this.key = key;
this.value = value;
}
public String getKey() {
return key;
}
public Integer getValue() {
return value;
}
}
// ...
}
Java
복사
key와 value 한 쌍을 저장하기 좋게 Node 객체를 만들었어요.
List<Node>[]
key와 value 한 쌍을 담은 Node객체를 담은 리스트의 배열…. 그림으로 보면
List<Node>[] table = new List[100];
Java
복사
코드를 처음부터 차근차근 보면, List를 선언한다 그 리스트안에는 Node 객체가 들어간다. 그리고 그 Node가 담겨있는 List의 배열([])을 만든다는 뜻이다.
String[] strArr = new String[5];
Java
복사
위 코드는 흔히보던 문자열이 담긴 배열을 말한다. [] 앞의 타입으로 배열을 만든다는 뜻이다.
그럼 [String, String, String, String, String] 배열이 만들어질 것이다.
다시 table 선언 코드를 보자.
[] 배열이다. 배열인데 List 가 담긴다. 그리고 그 List 에는 Node 가 들어간다.
[List<Node>, List<Node>, List<Node>, List<Node>, ... ]
