Hash chain I wanted to avoid (2)

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

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 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
[Failure] I wanted to generate sentences using Flair's TextRegressor
I wanted to modify Django's admin site a bit
I wanted to solve the Panasonic Programming Contest 2020 with Python
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 skip certain extensions when building Sphinx documentation
I wanted to worry about execution time and memory usage
I captured the Touhou Project with Deep Learning ... I wanted to.
I made my own OSS because I wanted to contribute to it
I wanted to calculate an array with Sympy's subs method
I wanted to delete multiple objects in s3 with boto3
I tried to learn PredNet
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 touch jupyter
I tried to implement StarGAN (1)
I wanted to do it like running an AtCoder test case.
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 do something like an Elixir pipe in Python
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]