Good evening. Thank you for your continued support. m (_ _) m
Continuing from the previous session. I wrote it smoothly Supplement about dump.
test.py
def dump(self):
#i is table[*]Because it is a pointer to table[i]
for i in range(self.capacity):
# table[i]The key stored in,value,Call np
p = self.table[i]
# end=""Is a description that connects to the next print
print(i,end="")
while p is not None:
#Display the following description immediately after i above
# p.key , p.Continue to display value
print(f"=>{p.key}({p.value})",end="")
#Substituting np for p to the next key,value,Connect to np
p = p.np
#new line
print()
If there is an image that stores data with the beads that I wrote last time I think it's easy to imagine.
Until now, using the Hash chain, I have stored the data. Now that we have stored it, let's challenge the approach of searching for data in it. Basically, it searches for data by associating it with the key in the Node that is already stored.
test.py
def search(self,key):
#Find the pointer of table from key.
Vhash = key % self.capacity
p = self.table[Vhash]
while p is not None:
#When the stored key and the input key match. ..
if p.key == key:
#View data with print
return print(f"searched value is {p.value}")
p = p.np
#If there is nothing even if you search for the corresponding data to the end with while, faile
print("faile to search")
If you are looking for it by adding it to the prepared array, You can also delete unnecessary items, right? Let's challenge. Same as search, basically find the corresponding Node by key. After that, change the connection point from Node to Node to complete the deletion. Yes, we will edit the np inside the Node.
test.py
def remove(self,key):
Vhash = key % self.capacity
p = self.table[Vhash]
pp = None #Initial value None
while p is not None:
if p.key == key
#Description when deleting the first data
if pp is None:
self.table[Vhash] = self.table[Vhash].np
#Edit connection points np other than the first item
else:
#pp will be described later, but the image is Node before the key corresponds.
#p is the Node to which the key corresponds.
# pp.By substituting np of the Node whose key corresponds to np
#Delete the key corresponding Node from the data connection
pp.np = p.np
#If p at the beginning.key !=If it is a key, substitute p for pp to buffer
pp = p
#Set the value of p to p to advance to the tip Node with while.Updated with np
p = p.np
I didn't explain what Hash is ?? My understanding is that by setting a key, you can get a pointer to the corresponding array in one shot. You can find it, and then you can find the corresponding value by linear search. It was an interesting search method. Of course, in order to achieve the above, it must be stored according to that rule.
The articles so far have been organized from a given arrangement or from the same arrangement. The exploration approach was basic.
This time it is not so, review the storage method itself It was an interesting algorithm that made it easier to explore. (`) No
I will put the whole picture. There is an optimal plan If you have any problems, please let me know. 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
Recommended Posts