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

こんばんは(*´ω｀)
題名には、思わず心の声が入っちゃいました(笑)
初めて勉強する人は私を含めイメージが難しかったのではないでしょうか？
なるべく分かりやすく、さぁ、飛び込んでみましょう。


取り急ぎ、適当な配列を用意しました。
これから適当なデータを以下の配列に格納していきます。
普通ならポインタ 0(=x[0]) から順にデータを格納するのですが、今回は趣向を変えましょう。
![図1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/2be46371-0809-5341-58f5-49e003bf41e8.png)
今回挑戦する Hash chain は
**１つのアドレスには 1つのデータしか格納できませんでしたが、
もっと沢山詰め込めないか !! っていうアプローチです。**(ちょっと乱暴ですかね。。)
有識者の方の資料を拝見すると以下のような図をよく見かけます。
![図2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/23c3cb81-c40d-0394-7961-4c5f3a80c5b2.png)
x[0]であれば、データが紐づいて合計 3 つ鎖で繋がっているように見えます。
初めて見た時、とっても素敵だと思いました、こんなこと出来るって凄い!!
でも、どうやって書くんだ、それ？(;´･ω･)

まずは、Hash の基本的な定義から行きます。
格納先のポインタはどうやって決めますか？
はい、これです。

**"ユーザが任意に指定する整数" % 配列長**

例えば**14**を入力すると今回用意した配列長は 7 なので 0 が出てきます。
OK, じゃあ、x[0] に何を格納しますか？

取りあえず **1** でも入れておきましょう。
いやいや stop!! x[0]格納するのは 1 だけじゃないんです、**14**も一緒に格納するんです!

疑問が死ぬほど出てきますが、このまま行きましょう。
表題にある通り chain(鎖) なので繋がり先のアドレスも入れておきましょう!!
key = 14 , value = 1 , np(next pointer) = none とすると以下の図になります。
![図3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/0fd2fe3a-3517-aa85-0b48-435f0af5abb8.png)
では、次の入力で key = 21 としたら、どうなりますか？
**21%7 = 0**
また **0** だ ('Д')
どうしよう。。。

困ったときは取りあえず書いてみると気分転換になります。

```test.py
class Node:
    
    def __init__(self,key,value,next):
        self.key = key     # ユーザ入力の任意の整数
        self.value = value # 格納したい値
        self.np = np       # next pointer
```

Node と定義して、その中には 3 つの引数が用意されています。
この Node を格納する配列を用意しましょう。

```test.py
class ChainedHash:
    def __init__(self,capacity):
        self.capacity = capacity # 配列長なので、あとで 7 を代入します
        self.table = [None]*self.capacity # Nodeを格納する配列を tableと命名
```

例えば、key = 14,value = 1,np = None を適当に Node に代入し、
更にそれを table[0] に代入し print してみます。
すると、ビックリ以下のようになった。

```test.py
[<__main__.Node object at 0x00000282E2DA9D60>, None, None, None, None, None, None]
```

なんだこれ、Node を table[0] に代入したら大変なことになった。
最初見た時は、思わず倒れそうになりました(笑)
でも今思うと、これも chain 方を構成するための 1 つのミソなのではないかと思います。

例えばですが、こんな記述を目にしたら、どう思いますか？

```test.py
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
```

冒頭に用意した Node に key, value, self.table[Vhash] の 3 つを
代入し、temp に代入しています。
key , value は、これから入力しようとしている値です。
でも self.table[Vhash], これは何でしょうか？
そう、これは、もともと table[0] に格納されていた値です。
もともと格納されていた table[0] の値には勿論、key , value, self.table[Vhash] が
格納されています(table[0] の初期値は None です。)。これは、何を意味するのでしょうか。。
ボキャ貧な説明を補うために、イメージを作ってみました。

![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/0fc08227-11aa-f536-e813-c978b101ad56.png)

最初に書き込んだのはデータ(key,value,np)は長いので A とします。
その後 B 同様に x[0] へデータを書き込みましたが、図にあるBの np を見てください。
A のデータそのものが埋め込まれていませんか？？
よって、最後に table[0] に格納された値 B の中身を把握した時には、次の A の値も見えるわけです。
このように、データの中にデータを埋め込む処理を続けると、いくつもデータが繋がって見えませんか？
念のため、もう一度前述の説明を念頭にもう一度記述を眺めてみてください。

```test.py
                      # ↓ Data A = self.table[0] 
temp = Node(key,value,self.table[Vhash])
#self.table[0] に 新たに用意した key + value + Data A をワンパッケージ化し代入
self.table[Vhash] = temp
#以上から table[0] の値は A から B へ更新されます
```

ね？(笑)
１つのアドレスに書き込むデータは 1 つだけど、
データの中にデータを埋め込んでるから、チェーンのように
繋がって見えるんです。
面白いですね(≧▽≦)

このイメージがあると、次が楽です。データの埋め込み作業の前に
もともと table[0] には重複データが無いか確認する記述が必要ですよね？
多分、このようになると思います。

```test.py
    def add(self,key,value):
        
        Vhash = key % self.capacity # table のどのポインタを指定するか算出
        p = self.table[Vhash]       # 0 だったとすると table[0] の値を p に代入
                                    # ここで p には key,value,np が入っています
        
        while p is not None:
            #p.key は p の中にある key だけを抜き出しています
            #p.key が今回入力した key と同等の場合は
            #重複するので使えませんので False を返します
            if p.key == key:
                return False
            #p の中にある np を呼び出し、
            #埋め込まれたデータ key, value, np を p に代入しなおします。
            p = p.np
            #冒頭の while に戻って、none になるまで続けて
            #重複する key が使われていないかを確認します。
        
        temp = Node(key,value,self.table[Vhash])
        self.table[Vhash] = temp
```

さぁ、やっとここまで来ました。
ザクっと全体像をまとめておきます。

```test.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()

test = ChainedHash(7)

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

```実行結果.py
select 1.add, 2.dump 1# 1.add を選択

key: 7

val: 1

select 1.add, 2.dump 1 # 1.add を選択

key: 14

val: 2

select 1.add, 2.dump 2# 2.dump を選択
0=>14(2)=>7(1) # chain の完成 ('Д')!!
1
2
3
4
5
6
```

うーん、説明が長くて、申し訳ないです。
続きは、その(2)へ続く...

**その後**
2020_11_08: 改めて自分の記事を読み返す。
そして書いてみる。
最後に改めて記事を読み直す。。。あれ?
なんか間違ってない!?(笑)
かなり時間が経って申し訳ありませんが、
以下にある add について補足致します。

```hash_add.py
    def add(self,key,value):
        #step 1:注目するポインタを定める
        Vhash = key % self.capacity 
        #step 2: 既に同一キーで格納していないか確認
        #          sel.table[Vhash] を p という箱に入れて確認する
        p = self.table[Vhash]      
        
        # p の中身を徹底的に掘る : p の中を線形探索
        while p is not None:
            if p.key == key: #同一キー発見!!
                return False #追加は出来ません!
            p = p.np         #p の中身を np に更新
        #晴れて同一キーがない事を確認できました。

        #step 3: Node の追加
        #では追加です。。でもどうやって追加する??
        #                       ↓もともとあったデータだよね？
        temp = Node(key,value,self.table[Vhash])
        # 新規追加する Node の np に既存のデータを埋め込み
        self.table[Vhash] = temp 

```

っということは、以下の図は。。
![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/0fc08227-11aa-f536-e813-c978b101ad56.png)
正しくはこうじゃない？
![図5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f75c644c-753e-2cab-7182-9ce224c42d69.png)
お詫びして訂正いたしますm(_ _)m