> 자료구조 구현/해시 테이블3 해시 충돌(hash collision) 해결(2) - 해시테이블 저장 공간 사용 2. Linear Probing 기법 - 폐쇄 해싱(Close Hashing): 충돌시, 해시테이블 저장 공간을 이용해 데이터를 연쇄적으로 연결시켜 저장하는 기법 hash_table = list([ 0 for i in range(6)]) def get_key(data): return ord(data[0]) + ord(data[1]) # address는 같아도 key값은 다르게 함 def hash_func(key): return key % 6 def save(data, value): index_key = get_key(data) address = hash_func(index_key) if hash_table[address] != 0: # 0이 아니면 주소에 data가 들어가 있다! for x in rang.. 2020. 10. 6. 해시 충돌(hash collision) 해결(1) - 링크드 리스트 사용 1. Chaining 기법 - 개방 해싱(Open Hasing): 충돌시, 링크드 리스트를 이용해 데이터를 연쇄적으로 연결시켜 저장하는 기법 hash_table = list([ 0 for i in range(6)]) def get_key(data): return ord(data[0]) + ord(data[1]) # address는 같아도 key값은 다르게 함 def hash_func(key): return key % 6 def save(data, value): index_key = get_key(data) address = hash_func(index_key) if hash_table[address] != 0: # 0이 아니면 주소에 data가 들어가 있다! for x in range(len(hash_t.. 2020. 10. 5. 해시 테이블(hash table)의 기본 * 해시(Hash): 임의의 데이터를 고정 길이의 데이터로 매핑하는 것 (Key는 고정 길이일 수도, 아닐 수도) * 해시 테이블(Hash table): Key에 Value를 저장하는 자료 구조 - Key 값을 통해 직접 Value 값에 접근이 가능하다 - 보통 배열로 해시 테이블 공간만큼 생성하여 사용한다 - 대표적인 예: Python의 Dictionary 타입 (python에서는 이 타입을 이용하면 되기 때문에 해시 테이블을 굳이 구현할 필요가 없다) * 해시 값(Hash value): Key값을 받은 해싱 함수가 특정 연산을 시행하여 반환해주는 값 (고정된 길이) 이를 통해, 해시 테이블에서 Key에 맞는 Value 값을 일관되게 찾을 수 있다 (Key값을 구하는 함수를 따로 만들 수 있다) has.. 2020. 10. 5. 이전 1 다음