Hash chain I wanted to avoid (1)
Good evening (* ´ω ｀) The title had a voice of my heart (laughs) I think it was difficult for people studying for the first time, including myself, to have an image. Make it as easy to understand as possible, and let's jump in.
I hurried and prepared an appropriate array.
From now on, we will store appropriate data in the following array.
Normally, data is stored in order from pointer 0 (= x [0]), but let's change the taste this time.
The Hash chain to challenge this time
** Only one data could be stored at one address,
Isn't it possible to pack more? !! ** (Is it a bit rough ...)
If you look at the materials of experts, you will often see the following figures.
If it is x [0], it looks like the data are linked and connected by a total of three chains.
When I first saw it, I thought it was very nice, it's amazing to be able to do this !!
But how do you write it? (; ´ ･ ω ･)
Let's start with the basic definition of Hash. How do you decide the pointer of the storage destination? Yes, this is it.
** "integer arbitrarily specified by the user"% Array length **
For example, if you enter ** 14 **, the array length prepared this time is 7, so 0 will appear. OK, so what do you want to store in x [0]?
For the time being, let's put in ** 1 ** as well. No, stop !! x [0] Not only 1 is stored, ** 14 ** is also stored together!
Questions will come up to death, but let's keep going.
As the title says, it's a chain, so let's enter the address of the connection destination !!
If key = 14, value = 1, np (next pointer) = none, the figure below will be obtained.
So what happens if you enter key = 21 with the following input?
21%7 = 0
Also ** 0 ** ('Д')
What should I do. .. ..
If you have a problem, try writing it for the time being and it will change your mood.
test.py
class Node:
def __init__(self,key,value,next):
self.key = key #Any integer entered by the user
self.value = value #Value you want to store
self.np = np # next pointer
We define it as a Node, which has three arguments. Let's prepare an array to store this Node.
test.py
class ChainedHash:
def __init__(self,capacity):
self.capacity = capacity #Since it is an array length, we will substitute 7 later.
self.table = [None]*self.capacity #Name the array that stores Nodes table
For example, assign key = 14, value = 1, np = None to Node as appropriate, Then assign it to table [0] and print it. Then, I was surprised to see the following.
test.py
[<__main__.Node object at 0x00000282E2DA9D60>, None, None, None, None, None, None]
What's wrong with assigning Node to table [0]? When I first saw it, I almost fell down (laughs) But now that I think about it, I think this is also one of the ways to make up the chain.
For example, what do you think when you see this description?
test.py
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
Key, value, self.table [Vhash] are added to the Node prepared at the beginning. Substitute and assign to temp. key and value are the values you are about to enter. But self.table [Vhash], what is this? Yes, this is the value originally stored in table [0]. Of course, key, value, self.table [Vhash] are included in the value of table [0] that was originally stored. It is stored (the initial value of table [0] is None). What does this mean. .. I made an image to supplement the poor explanation.
The first thing I wrote is A because the data (key, value, np) is long. After that, I wrote the data to x [0] like B, but look at B's np in the figure. Is the data of A itself embedded? ?? Therefore, when we finally grasp the contents of the value B stored in table [0], we can also see the next value of A. If you continue the process of embedding data in the data like this, do you not see many data connected? Just in case, please look at the description again with the above explanation in mind.
test.py
# ↓ Data A = self.table[0]
temp = Node(key,value,self.table[Vhash])
#self.table[0]Newly prepared key+ value +Data A in one package and assigned
self.table[Vhash] = temp
#From the above table[0]The value of is updated from A to B
Right? (Lol) Only one data is written to one address, Because the data is embedded in the data, like a chain It looks like they are connected. It's interesting (≧ ▽ ≦)
With this image, the next is easier. Before embedding data Originally, table [0] needs a description to check if there is duplicate data, right? Maybe it will be like this.
test.py
def add(self,key,value):
Vhash = key % self.capacity #Calculate which pointer to specify in table
p = self.table[Vhash] #If it is 0, table[0]Substitute the value of into p
#Where p is key,value,Contains np
while p is not None:
#p.key extracts only the key in p
#p.If the key is equivalent to the key you entered this time
#It cannot be used because it is duplicated, so it returns False.
if p.key == key:
return False
#Call np inside p,
#Embedded data key, value,Reassign np to p.
p = p.np
#Go back to while at the beginning and continue until none
#Check for duplicate keys.
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
Well, I'm finally here. I will summarize the whole picture quickly.
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
Execution result.py
select 1.add, 2.dump 1# 1.Select add
key: 7
val: 1
select 1.add, 2.dump 1 # 1.Select add
key: 14
val: 2
select 1.add, 2.dump 2# 2.Select dump
0=>14(2)=>7(1) #Completion of chain('Д')!!
1
2
3
4
5
6
Well, I'm sorry for the long explanation. The continuation continues to that (2) ...
Recommended Posts