목록기본개념/알고리즘공부 (11)
VioletaBabel
해시테이블 (hash table)
key를 value에 대응시키는 자료구조. 연결 리스트와 해시 코드 함수를 이용하면 간단하게 구현할 수 있음. 키와 값을 해시테이블에 넣는 과정1. 키의 해시 코드 계산. (키는 보통 int, long. 키는 무한하나 int는 유한하기 때문에 서로 다른 키가 해시코드를 가리킬 수 있음)2. hash(key)%array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구함(같은 인덱스를 가리킬 수도 있음)3. 배열의 각 인덱스에 키와 값으로 이루어진 연결리스트가 존재. 키와 값을 해당 인덱스에 저장(충돌을 대비해 연결리스트 이용). 충돌이 많은 최악의 경우는 O(N) [N은 키의 갯수]잘 구현된 경우엔 O(1) ----- 문자열(키)을 정숫값(해시 코드)로 치환해 문제를 해결하는 방법은 주..
기본개념/알고리즘공부
2017. 9. 5. 15:10