데이터구조-해시 테이블(Hash Table)

*데이터구조-해시 테이블(Hash Table)

-데이터 검색을 효율적으로 하기위해 사용되는 구조

-키(Key)와 값(Value)이 한 쌍을 이루는 데이터를 저장함

-일반적으로 키는 데이터 식별자이며, 값은 데이터의 내용으로 생각할 수 있음

-해시테이블은 해시 함수를 이용해 배열 내의 특정 데이터에 빠르게 접근할 수 있음

-해시함수 : 주어진 데이터를 고정 길이의 불규칙한 숫자로 변환하는 함수

-해시 함수로 얻은 해시 값은 충돌 시 리스트 사용하여 기존 데이터의 뒤에 연결(연쇄법, 체이닝)

 

 

*해시테이블 저장

-키(Key)와 값(Value)이 한 쌍을 이루는 데이터 저장

-해시함수(주어진 데이터를 고정 길이의 불규칙한 숫자로 변환하는 함수)와 함께 데이터 검색을 함

-해시테이블 사용하기(ex. 키 값 : 이름, 데이터 : 성별(M, F), 배열 5개(0~4번방))

-해시테이블은 해시함수를 이용해 검색할 키에 해당하는 해시값 계산(ex. 문자열 키 Cho에 해당하는 해시값 -> 4928)

-계산하여 나온 해시값을 배열의 상자 수로 나누어 나머지(mod 연산)를 구함(ex. 4928 mod 5 = 3)

-나머지를 구하는 mod연산 결과 값에 해당하는 배열의 위치에 키와 데이터 저장(ex. 배열의 3번방에 키값 Cho와 데이터 F 저장 )

-이 처리를 반복해 다른 데이터도 하나씩 채워감

-만약 해시값을 mod연산하여 나온 값 중 이미 저장된 방의 값이 나온 경우 '충돌'이 발생함

-충돌이 발생한 경우 리스트 구조(데이터를 일직선으로 나열한 형태)로 기존 데이터와 연결

 

생성된 해시테이블 구조

 

*해시테이블 데이터 검색

-ex. Dan의 성별 검색

--키값인 Dan의 해시값을 구하고 배열의 상자 수5로 mod연산(Dan -> 1539 mod 5 = 4)

--4번 방에 키값 Dan이 저장되어 있고 키 값에 대응하는 데이터 값 추출 -> M값이 추출됨

 

-ex. Ally의 성별 검색

--Ally 해시 값 (9143) -> 9143 mod 5 = 3

--3번 방에 키 값 Cho가 저장되어 있으므로 키 값 불일치

--Cho의 데이터를 선두로 만들어진 리스트를 대상으로 선형탐색 시작

--키 값 Ally 데이터 발견 후 대응하는 데이터 값 추출 -> F 추출됨

 

 

*해시테이블 사용

-배열은 데이터를 저장하고 특정 값을 탐색할 때 앞에서부터 차례대로 확인(선형탐색)함

-선형탐색을 하면 데이터양에 비례해 계산 시간이 늘어나며 탐색에서는 적합하지 않은 구조임

-해시테이블은 배열의 문제점을 해결할 수 있음

-해시테이블은 데이터의 유연한 저장과 빠른 접근이 가능하여 프로그래밍 언어의 연관배열 등에 사용됨

 

 

 

 

---

이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다.