해시법3 알고리즘 - 해시법(3) 이번에는 해시법 중에서 오픈 주소법입니다. 오픈 주소법은 충돌이 발생했을 때 재해싱으로 빈 곳을 찾는 방법을 말합니다. ㅡ 14 ㅡ 29 ㅡ 5 6 ㅡ 이렇게 배열이 있을 때, 칸 하나하나를 버킷이라고 부릅니다. 만약 숫자를 추가해야 하는데 버킷이 이미 다른 숫자가 들어와 있다면 빈 버킷을 찾아 이동하게 만드는 것입니다. 오픈 주소법도 체인법과 마찬가지로 파일을 2개로 분리하겠습니다. open_hash.py from __future__ import annotations from typing import Any, Type from enum import Enum class Status(Enum): OCCUPIED = 0 EMPTY = 1 DELETED = 2 class Bucket: def __init__(.. 2020. 11. 2. 알고리즘 - 해시법(2) 저번 포스팅에 이어서 체인법입니다. 이번에는 노드를 key, value, next 이렇게 세 가지로 구성해서 key 값도 넣겠습니다. 또한 value가 str형일 때 hashlib을 사용해 해시값을 구해보겠습니다. chain_hash.py from __future__ import annotations from typing import Any, Type import hashlib class Node: def __init__(self, key: Any, value: Any, next: Node) -> None: self.key = key # 키 self.value = value # 값 self.next = next # 뒤쪽 노드 참조 class ChainHash: def __init__(self, capac.. 2020. 10. 27. 알고리즘 - 해시법(1) 이진 검색에 이어 해시법입니다. 해시법 해시법은 데이터를 저장할 위치를 간단하게 연산으로 구하는 방법입니다. 이 방법은 데이터의 검색뿐만 아니라 추가, 삭제도 효율적으로 할 수 있습니다. 배열에서 각각의 원소 값을 배열의 크기로 나누어 원소에 접근할 때 기준 값으로 합니다. 원소 값 5 6 20 31 37 53 78 해시값 (7로 나눔) 5 6 6 3 2 4 1 해시값을 배열의 인덱스로 생각하고 다시 만들어 보면 인덱스 0 1 2 3 4 5 6 원소 None 78 37 31 53 5 6 20 만약 숫자 21을 추가한다면 다른 원소들을 이동할 필요 없이 21을 7로 나눈 값인 0에 넣어주면 됩니다. 인덱스 0 1 2 3 4 5 6 원소 21 78 37 31 53 5 6 20 하지만 문제가 있습니다. 6번 .. 2020. 10. 26. 이전 1 다음
