해시테이블(hash table)
프로그래밍/Unity2016.10.18. 18:36
1.희소자료(sparse data)
게임 안에서 각 플레이어를 식별번호(KEY)로 구별한다. 각 키는 고유하여
동일한 키를 가지는 플레이어는 없다. 또, 0~ 1000,000 사이의 정수로 무작위 결정된다.
EX) player1 : 945,253
player2: 433,455
player3: 36,549
|
|
player3(36,549) |
|
player2(433,455) |
|
player1(945,253) |
|
0 100,0000
-> 1000,000개의 색인들 중 3개의 색인만 쓰여서 무지 낭비.
배열이 아닌 연결리스트로 구현해도 연결리스트 자체가 접근속도가 느려서 별 소용없다.
!-> 그래서 해시테이블 사용!
키 기반 희소자료를 적당한 크기의 공간에 빠르게 저장할 수 있다.
'특정한' 하나의 키가 테이블 안에 존재하는지의 여부를 빠르게 판단할 수 있다.
->키의 해시코드에 따라 구성된 키/값 쌍의 개체를 저장한 컬렉션.
2. 나머지 연산을 통한 해싱
키가 945,253인 플레이어1을 적당한 크기의 공간에 10인 배열에 넣는다고 할 때,
나머지 연산을 통해서 넣는다.
ex) 키를 배열의 크기 10으로 나눈다.
player1: 3
player2: 5
player3: 9
|
|
|
|
p1 |
|
p2 |
|
|
p3 |
0 3 5 9
배열에서 특정 플레이어를 조회할 때도 동일한 방법을 사용한다.
ex) player = table [key&10];
나머지를 구하는 해싱은 문제가 많지만 충분히 해시테이블의 중요성을 알수 있다.
이상적인 해시테이블은 항목의 검색 알고리즘이 'O(c)'이다.