こんばんは(*´ω｀)
題名には、思わず心の声が入っちゃいました(笑)
初めて勉強する人は私を含めイメージが難しかったのではないでしょうか？
なるべく分かりやすく、さぁ、飛び込んでみましょう。
取り急ぎ、適当な配列を用意しました。
これから適当なデータを以下の配列に格納していきます。
普通ならポインタ 0(=x[0]) から順にデータを格納するのですが、今回は趣向を変えましょう。
今回挑戦する Hash chain は
１つのアドレスには 1つのデータしか格納できませんでしたが、
もっと沢山詰め込めないか !! っていうアプローチです。(ちょっと乱暴ですかね。。)
有識者の方の資料を拝見すると以下のような図をよく見かけます。
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 とすると以下の図になります。
では、次の入力で key = 21 としたら、どうなりますか？
21%7 = 0
また 0 だ ('Д')
どうしよう。。。
困ったときは取りあえず書いてみると気分転換になります。
class Node:
def __init__(self,key,value,next):
self.key = key # ユーザ入力の任意の整数
self.value = value # 格納したい値
self.np = np # next pointer
Node と定義して、その中には 3 つの引数が用意されています。
この Node を格納する配列を用意しましょう。
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 してみます。
すると、ビックリ以下のようになった。
[<__main__.Node object at 0x00000282E2DA9D60>, None, None, None, None, None, None]
なんだこれ、Node を table[0] に代入したら大変なことになった。
最初見た時は、思わず倒れそうになりました(笑)
でも今思うと、これも chain 方を構成するための 1 つのミソなのではないかと思います。
例えばですが、こんな記述を目にしたら、どう思いますか？
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 です。)。これは、何を意味するのでしょうか。。
ボキャ貧な説明を補うために、イメージを作ってみました。
最初に書き込んだのはデータ(key,value,np)は長いので A とします。
その後 B 同様に x[0] へデータを書き込みましたが、図にあるBの np を見てください。
A のデータそのものが埋め込まれていませんか？？
よって、最後に table[0] に格納された値 B の中身を把握した時には、次の A の値も見えるわけです。
このように、データの中にデータを埋め込む処理を続けると、いくつもデータが繋がって見えませんか？
念のため、もう一度前述の説明を念頭にもう一度記述を眺めてみてください。
# ↓ 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] には重複データが無いか確認する記述が必要ですよね？
多分、このようになると思います。
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
さぁ、やっとここまで来ました。
ザクっと全体像をまとめておきます。
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
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 について補足致します。
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
っということは、以下の図は。。
正しくはこうじゃない？
お詫びして訂正いたしますm(_ _)m