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. 図1.PNG 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. 図2.PNG 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. 図3.PNG 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.

図4.PNG

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

Hash chain I wanted to avoid (2)
Hash chain I wanted to avoid (1)
I wanted to evolve cGAN to ACGAN
I wanted to solve ABC160 with Python
I wanted to solve ABC159 in Python
I wanted to solve ABC172 with Python
I really wanted to copy with selenium
Implemented DQN in TensorFlow (I wanted to ...)
I wanted to solve NOMURA Contest 2020 with Python
i-Town Page Scraping: I Wanted To Replace Wise-kun
I wanted to play with the Bezier curve
I wanted to install Python 3.4.3 with Homebrew + pyenv
I just wanted to understand Python's Pickle module
I also wanted to check type hints with numpy
I started to analyze
I wanted to use the Python library from MATLAB
I tried to debug.
I tried to paste
I wanted to modify Django's admin site a bit
I tried to automatically create a report with Markov chain
[Markov chain] I tried to read negative emotions into Python.
I wanted to classify Shadowverse card images by reader class
[Markov chain] I tried to read a quote into Python.
I wanted to worry about execution time and memory usage
I wanted to delete multiple objects in s3 with boto3
I tried to organize SVM.
I talked to Raspberry Pi
I tried to implement PCANet
Introduction to Nonlinear Optimization (I)
I applied LightFM to Movielens
I want to solve Sudoku (Sudoku)
I tried to reintroduce Linux
I tried to introduce Pylint
I tried to summarize SparseMatrix
I tried to implement StarGAN (1)
I wanted to do it like running an AtCoder test case.
I wanted to create a smart presentation with Jupyter Notebook + nbpresent
I wanted to convert my face photo into a Yuyushiki style.
I wanted to challenge the classification of CIFAR-10 using Chainer's trainer
I wanted to solve the ABC164 A ~ D problem with Python
What I did when I wanted to make Python faster -Numba edition-
[Django] I wanted to test when POSTing a large file [TDD]