해쉬(Hash) 테이블
공부하는 내용 정리
프로그래밍 부트캠프를 하면서, 간단한 Hash 예제 연습을 하면서, 배운 내용에 대해 정리하고자 한다.
Hash를 사용하기에 좋은 예는 '전화번호부' 관리이다.
출처: Department of Engineering - University of Cambridge위 그림과 같이 존 스미스 씨와 리사 스미스 그리고 샘 도씨의 전화번호를 그냥 배열에 저장해 볼 수 있다. 이후 그들의 전화번호를 추출하기 위해서는 , 모든 배열 요소의 이름을 하나씩 확인하여, 구하려는 사람의 이름이 일치할 경우 번호를 꺼내면 된다. 그런데 동일한 결과를 얻기 위해 배열 대신 Hash 테이블을 이용하면 전화번호 추출 속도를 개선할 수 있다.
출처: Wikibooks각 사람의 이름 string 값을 이 미스테리한 Hash함수에 넣어 돌리면 Hash('string') = 어떠한 값 으로 받을 수 있다. 이 Hash 함수는, key로 들어오는 값에 따라 다소 복잡하게 조작해서 Hash 함수 결과값이 최대한 고유한 결과값이 나오도록 설계한다. 보통 직접 Hash 함수를 설계하기보다는 이미 잘 만들어져 있는 Hash 함수를 사용하게 된다. 실제로는 Hash 함수 결과값을 관리하고자 하는 Index 길이 값으로 나눈 나머지 값을 실제 사용할 Index로 놓는다. 이후 각 Index 배열 위치에 사람 이름과 전화번호를 Key-value pair로 저장하게 된다.
장점은 이제 나온다.
기존에 배열에서 각 사람의 이름을 각 배열의 index마다 찾아야 했다면, 이제는 찾으려는 사람의 string값을 Hash를 돌려 특정 index값을 받게 되면, 바로 그 특정 index가 가리키는 정보를 추출할 수 있다.
이름 -> Hash(이름) -> 고유 index -> 전화번호 추출
순으로 빠르게 특정 사람의 전화번호를 가지고 올 수 있다.
