해싱(hashing)

해싱(hashing)

 

- 해시함수를 이용해 데이터를 저장하고 읽어올 수 있다.

- 해시함수(hash function)로 해시 테이블(hash table)에 데이터를 저장하고, 검색한다.

- 해시테이블은 배열과 링크드 리스트가 조합된 형태다.

 

[ 해시테이블에 저장된 데이터를 가져오는 방법]

1. 키로 해시함수를 호출해서 해시코드(배열의 index)를 얻는다

2. 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다.

3. 링크드리스트에서 키와 일치하는 데이터를 찾는다.

※ 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다.

    서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.