避けて通りたかった Hash chain その(2)

こんばんは。
いつも応援有難う御座います。m(_ _)m

前回の続きです。
サラっと書いておいた
dump について補足します。

test.py

    def dump(self):
        # i は table[*] のポインタなので table[i] 
        for i in range(self.capacity):
            # table[i] に格納されている key,value,np を呼び出す 
            p = self.table[i]
            # end=""は、次の print と繋げる記述
            print(i,end="")
            while p is not None:
                #前述 i のすぐ後に以下の記述を表示
                # p.key , p.value を続けて表示
                print(f"=>{p.key}({p.value})",end="")
                # p に np を代入して次の key,value,np に繋げる
                p = p.np
            #改行
            print()

前回書いた数珠つなぎでデータを格納するイメージがあれば
何となくイメージしやすいと思います。

今まで、Hash chain を使って、
データを格納してきました。
格納したのだから、その中からデータを探すアプローチにもチャレンジしましょう。
基本的には既に格納されている Node の中の key に紐づけてデータを探します。

test.py

    def search(self,key):
        # key から table のポインタを割り出します。
        Vhash = key % self.capacity
        p = self.table[Vhash]
        
        while p is not None:
            # 格納された key と入力 key が一致した場合。。
            if p.key == key:
                # データを print で表示
                return print(f"searched value is {p.value}")
            p = p.np
        # while で最後まで該当データを探しても何もない場合、faile
        print("faile to search")

用意した配列に追加して、探したのであれば、
不要項目を削除することも出来ますよね？
チャレンジしてみましょう。
search と同じで、基本的には key で該当 Node を見つけます。
そのあとに、Node から Node の接続点を変えれば削除完了です。
そう、Node 中にある np を編集していきます。

test.py

    def remove(self,key):
        Vhash = key % self.capacity
        p  = self.table[Vhash]
        pp = None # 初期値 None 
        while p is not None:
            if p.key == key
                #最初のデータを削除する場合の記述
                if pp is None:
                    self.table[Vhash] = self.table[Vhash].np
                #最初の項目以外の接続点 np を編集
                else:
                    # pp は後述するがイメージはkey が該当する前の Node
                    # p は key が該当した Node。
                    # pp.np に key が該当した Node の np を代入することで
                    # データの繋ぎから key 該当 Node を削除
                    pp.np = p.np
        # 冒頭の if p.key != key だった場合に pp には p を代入してバッファ
        pp = p            
        # while で先端 Node まで進むために p の値を p.np で更新
        p  = p.np

Hash とは何ぞや?? っという説明をちゃんとしていませんでした。
私の理解では、key を設けることで、該当する配列のポインタを一発で
見つけることができ、そのあとは、線形探索で該当値を探すことができる
面白い探索方法でした。
上記を実現するために勿論、その規則に沿って格納しなければならないです。

今までの記事は与えられた配列を整頓したり、そのままの並びから
探索するアプローチが基本でした。

今回はそうではなく、格納方法そのものを見直して
探索しやすくしている興味深いアルゴリズムでした。( ｀ー´)ノ

全体像を載せておきます。
最適案があったり、
問題があれば御教示よろしくお願い致しますm(_ _)m。

Chained_hash.py

class Node:
    def __init__(self,key,value,np):
        self.key = key
        self.value = value
        self.np = np

class ChainedHash:
    def __init__(self,capacity):
        self.capacity = capacity
        self.table = [None]*self.capacity
        
    def add(self,key,value):
        
        Vhash = key % self.capacity
        p = self.table[Vhash]
        
        while p is not None:
            if p.key == key:
                return False
            p = p.np
        
        temp = Node(key,value,self.table[Vhash])
        self.table[Vhash] = temp
    
    def dump(self):
        for i in range(self.capacity):
            p = self.table[i]
            print(i,end="")
            while p is not None:
                print(f"=>{p.key}({p.value})",end="")
                p = p.np
            print()
            
    def search(self,key):
        Vhash = key % self.capacity
        p = self.table[Vhash]
        
        while p is not None:
            if p.key == key:
                return print(f"searched value is {p.value}")
            p = p.np
        print("faile to search")
        
    def remove(self,key):
        Vhash = key % self.capacity
        p  = self.table[Vhash]
        pp = None
        while p is not None:
            if p.key == key:
                if pp is None:
                    self.table[Vhash] = self.table[Vhash].np
                else:
                    pp.np = p.np
        pp = p            
        p  = p.np

test = ChainedHash(7)

while True:
    num = int(input("select 1.add, 2.dump, 3.search, 4.remove : "))
    if num == 1:
        key = int(input("key: "))
        val = int(input("val: "))
        test.add(key,val)
    elif num == 2:
        test.dump()
    elif num == 3:
        key = int(input("key: "))
        test.search(key)
    elif num == 4:
        key = int(input("key: "))
        test.remove(key)
    else:
        break