【Python】ハッシュ法とチェイン法【アルゴリズム】

# チェイン法によるハッシュ

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 ChainedHash:
    """チェイン法を実現するハッシュクラス"""

    def __init__(self, capacity: int) -> None:
        """初期化"""
        self.capacity = capacity             # ハッシュ表の容量
        self.table = [None] * self.capacity  # ハッシュ表(すべてが空のリスト)

def hash_value(self, key: Any) -> int:
        """ハッシュ値を求める"""
        if isinstance(key, int):
            return key % self.capacity
        return (int(hashlib.sha256(str(key).encode()).hexdigest(), 16)
                % self.capacity)

def search(self, key: Any) -> Any:
        """キーkeyの要素の探索をして値を返却"""
        hash = self.hash_value(key)  # 探索するキーのハッシュ値
        current = self.table[hash]   # 着目ノード

        while current is not None:
            if current.key == key:
                return current.value # 探索成功
            current = current.next   # 後続ノードに着目

        return None                  # 探索失敗

def add(self, key: Any, value: Any) -> bool:
        """キーがkeyで値がvalueの要素を挿入"""
        hash = self.hash_value(key)  # 挿入するキーのハッシュ値
        current = self.table[hash]   # 着目ノード

        while current is not None:
            if current.key == key:
                return False         # 挿入失敗
            current = current.next   # 後続ノードに着目

        add_node = Node(key, value, self.table[hash])
        self.table[hash] = add_node  # ノードを挿入
        return True                  # 挿入成功

def remove(self, key: Any) -> bool:
        """キーがkeyの要素を削除"""
        hash = self.hash_value(key)  # 削除するキーのハッシュ値
        current = self.table[hash]   # 着目ノード
        current.prev = None          # 前回の着目ノード

        while current is not None:
            if current.key == key:   # キーを見つけた
                if current.prev is None:
                    self.table[hash] = current.next
                else:
                    current.prev.next = current.next
                return True          # 削除成功
            current.prev = current
            current = current.next   # 後続ノードに着目
        return False                 # 削除失敗(keyは存在しない)

def print(self) -> None:
        """ハッシュ表を表示"""
        for i in range(self.capacity):
            current = self.table[i]
            print(i, end='')
            while current is not None:
                print(f' → {current.key} ({current.value})', end='')
                current = current.next
            print()

# チェイン法によるハッシュ

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 ChainedHash:
    """チェイン法を実現するハッシュクラス"""

    def __init__(self, capacity: int) -> None:
        """初期化"""
        self.capacity = capacity             # ハッシュ表の容量
        self.table = [None] * self.capacity  # ハッシュ表(すべてが空のリスト)

    def hash_value(self, key: Any) -> int:
        """ハッシュ値を求める"""
        if isinstance(key, int):
            return key % self.capacity
        return (int(hashlib.sha256(str(key).encode()).hexdigest(), 16)
                % self.capacity)

    def search(self, key: Any) -> Any:
        """キーkeyの要素の探索をして値を返却"""
        hash = self.hash_value(key)  # 探索するキーのハッシュ値
        current = self.table[hash]   # 着目ノード

        while current is not None:
            if current.key == key:
                return current.value # 探索成功
            current = current.next   # 後続ノードに着目

        return None                  # 探索失敗

    def add(self, key: Any, value: Any) -> bool:
        """キーがkeyで値がvalueの要素を挿入"""
        hash = self.hash_value(key)  # 挿入するキーのハッシュ値
        current = self.table[hash]   # 着目ノード

        while current is not None:
            if current.key == key:
                return False         # 挿入失敗
            current = current.next   # 後続ノードに着目

        add_node = Node(key, value, self.table[hash])
        self.table[hash] = add_node  # ノードを挿入
        return True                  # 挿入成功

    def remove(self, key: Any) -> bool:
        """キーがkeyの要素を削除"""
        hash = self.hash_value(key)  # 削除するキーのハッシュ値
        current = self.table[hash]   # 着目ノード
        current.prev = None          # 前回の着目ノード

        while current is not None:
            if current.key == key:   # キーを見つけた
                if current.prev is None:
                    self.table[hash] = current.next
                else:
                    current.prev.next = current.next
                return True          # 削除成功
            current.prev = current
            current = current.next   # 後続ノードに着目
        return False                 # 削除失敗(keyは存在しない)

    def print(self) -> None:
        """ハッシュ表を表示"""
        for i in range(self.capacity):
            current = self.table[i]
            print(i, end='')
            while current is not None:
                print(f' → {current.key} ({current.value})', end='')
                current = current.next
            print()

# チェイン法を実現するハッシュクラスChainedHashの利用例

from enum import Enum
from chained_hash import ChainedHash

Menu = Enum('Menu', ['追加', '削除', '探索', '表示', '終了'])

def select_menu() -> Menu:
    """メニュー選択"""
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep=' ', end='')
        n = int(input(' : '))
        if 1 <= n <= len(Menu):
            return Menu(n)

hash = ChainedHash(13)       # 容量13のハッシュ表

while True:
    menu = select_menu()     # メニュー選択

    if menu == Menu.追加:    # 追加
        add_key = int(input('キー : '))
        add_value = input('値 : ')
        if not hash.add(add_key, add_value):
            print('追加できませんでした。')

    elif menu == Menu.削除:  # 削除
        remove_key = int(input('キー : '))
        if not hash.remove(remove_key):
            print('削除できませんでした。')

    elif menu == Menu.探索:  # 探索
        search_key = int(input('キー : '))
        search_value = hash.search(search_key)
        if search_value is not None:
            print(f'そのキーの値は{search_value}です。')
        else:
            print('そのキーにデータはありませんでした。')

    elif menu == Menu.表示:  # 表示
        hash.print()

    else:                    # 終了
        break

(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 1
キー : 2
値 : 吉川
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 1
キー : 6
値 : 坂本
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 1
キー : 8
値 : 丸
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 1
キー : 10
値 : 中田
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 1
キー : 21
値 : 井納
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 3
キー : 6
そのキーの値は坂本です。
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 4
0
1
2 → 2 (吉川)
3
4
5
6 → 6 (坂本)
7
8 → 21 (井納) → 8 (丸)
9
10 → 10 (中田)
11
12
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 2
キー : 21
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 4
0
1
2 → 2 (吉川)
3
4
5
6 → 6 (坂本)
7
8 → 8 (丸)
9
10 → 10 (中田)
11
12
(1)追加 (2)削除 (3)探索 (4)表示 (5)終了 : 5