반응형

IT/데이타 자료구조 2

자료구조 (해쉬테이블 2) 충돌 해결 알고리즘

해쉬 테이블의 가장 큰 문제는 충돌 이를 해쉬충돌이라고 한다. Chaining기법 개방 해싱, 오픈 해싱 기법 -해쉬 테이블 저장공간 외의 공간을 활용한다. -충돌이 일어나면 링크드 리스트라는 자료구조 사용해 충돌에 대응한다. Linear Probing 기법 폐쇄 해싱 또는 클로즈 해싱 기법 -해쉬 테이블 저장공간 내의 공간을 활용한다. -충돌이 일어나면 해당 해시 값의 다음 값부터 맨 처음 나오는 빈공간에 저장한다. 위와 같이 크게 두 가지 전략으로 충돌에 대해 대처한다. 우선 오픈 해싱 기법에 대해 구체적으로 알아보자 hash_table = list([0 for i in range(8)]) def get_key(data): return hash(data) def hash_function(key): r..

자료구조(해쉬테이블 1)

해쉬 테이블(Hash Table) 키(key)에 데이터(value)를 맵핑할 수 있는 자료 구조이다. -해쉬(Hash) : 방대한 데이터를 고정 길이로 변환하는 것 -해싱함수(Hashing Function) : 키를 산술 연산으로 이용하여 데이터 위치를 찾는 함수 -해쉬 값(해쉬 주소) : 해싱함수의 결과물 -슬롯(Slot) : 한개의 데이터를 저장할 수 있는 공간 name1 = 'Andy' name2 = 'Dave' name3 = 'Trump' hash_table = list([ 0 for i in range(10)]) def hash_func(key): return key % 7 def storage_data(data, value): key = ord(data[0]) hash_address = has..

반응형