해시 테이블의 컴퓨팅 사고

해시테이블은 키값이 있는 테이블이다.

[ ["사과", 1000] ["바나나",1500] ["포도",2000] ]

 

그럼 컴퓨터는 어떻게 값을 저장하고 읽어들일까..

 

먼저 문자를 숫자로 변환하는 해싱작업을 한다. 이때 각 문자는 지정되어 있는데

예를 들어 ABC라는 값은 A = 1, B = 2, C = 3 으로 되어있을경우 1*2*3 = 6 으로 해싱한다

ABC에 값으로 apple를 넣으면 아래 그림과 같이 표현된다.

"apple"

 

문제는 BAC에 pop이라는 값을 저장할때이다. 마찬가지로 2*1*3 = 6 이니 셀이 중복된다.

이때 해시는 배열처럼 자리를 나누어 저장한다.

["ABC","apple"]["BAC","pop"]

 

해시값을 찾을때는 선행검색으로 하나하나 차례대로 찾게 된다.

만약 중복된셀이 없으면 O(1) 단계이지만 중복이 된다면 O(N) 단계가 되어버린다.