해시 테이블

해시 테이블은 Key와 Value 로 데이터를 저장하는 자료구조 입니다.

 

해시 테이블은 해시 함수를 사용합니다. 해시 함수를 이용하여 key 값을 해시 value 를 생성합니다. 생성된 해시 value 를 배열의 인덱스로 하여 그 공간에 value 를 저장합니다. 값을 찾을 때에도 key 값을 해시함수에 넣어 해시 value 를 찾고 배열의 인덱스로 하여 value 를 찾습니다.

만약 해시 함수에 의해 나오는 해시 value 값이 같다면 충돌이 생기며,

1. 체이닝

2. 오픈 어드레스를 이용하여 해결합니다.

 

1. 체이닝 : 해시 테이블의 각 인덱스의 저장공간을 리스트로 만들어 충돌이 발생할 때 리스트를 이용하여 연결합니다.

2. 오픈 어드레스 : 충돌이 일어나면 다른 비어있는 공간을 찾고 저장합니다.

 

해시 테이블은 게임 오브젝트 관리 및 맵의 타일 관리 등에 사용될 수 있습니다.

 

해시 테이블 특징

 

해시 테이블은 Key 값에 해시 함수를 적용해 고유한 index 를 생성하여 해당 인덱스로 저장된 값을 꺼내오는 구조입니다. 고유한 index 로 임의 접근이 가능하기 때문에 평균적으로 O(1) 의 시간복잡도를 가지지만 index 충돌이 일어나면 해당 index와 연결된 데이터들을 값을 찾기 때문에 O(N)까지 증가할수있으며 이러한 충돌은 체이닝을 통해 해결합니다.

 

일반적으로 해시 테이블은 key 따른 정렬이 되지 않습니다.