python - 散列和使用双向链表解决冲突

Question

我试图弄清楚如何将在哈希列表中相同位置索引的列表值附加到该哈希索引的开头。我有双链表代码和使用单链表链接方法的散列代码我只是很难理解如何使用双链表来做到这一点。

这是我的代码：

# Collisions are resolved by chaining, except that instead of storing the
# collisions in a list, store them in a doubly-linked list. Use the doubly-linked
# list code below, but modify it to insert new elements at the beginning of the
# list instead of the end. You cannot use other modules.

import math


class Node(object):
    def __init__(self,data=None,next_node=None,prev_node=None):
        self.data=data
        self.next_node=next_node
        self.prev_node=prev_node


class DoubleLinkedList():
    def __init__(self,head=None):
        self.head=head

    def traverse(self):
        curr_node=self.head
        while curr_node != None:
            print(curr_node.data)
            curr_node=curr_node.next_node

    def get_size_list(self):
        #create a counter
        count=0
        curr_node = self.head

        while curr_node != None:
            #add to old count
           count=count+1
           curr_node = curr_node.next_node

        return count

    def prepend(self,data):
        #define new node
        new_node=Node(data)
        #set the next node equal to old head
        new_node.next_node=self.head
        #because its the head the prev point will point to nothing
        new_node.prev_node=None
        #handle the non-empty list case
        if self.head!=None:
            self.head.prev_node=new_node
        #update the head
        self.head=new_node

list_=[43,22,1,0,15,31,99,218,4,7,11,8,9]

hash_val= [[] for _ in range(13)]

Dlist=DoubleLinkedList()

def display_hash(hashTable):
    for i in range(len(hashTable)):
        print(i,end=" ")
        for j in hashTable[i]:
            print("-->",end=" ")
            print(j,end=" ")
        print()

def hash_func(list_):
    list_2=[None for i in range(13)]

    for i in list_:
        #print(math.floor((pow((key+6),3)/17+key)%13)
        hash_key=math.floor((pow((i+6),3)/17+i)%13)
        hash_val[hash_key].append(i)
        list_2[math.floor((pow((i+6),3)/17+i)%13)]=i

    print(list_2)
    print(list_)
    print(hash_val)
    print (math.floor((pow((43+6),3)/17+43)%13))
    print(math.floor((pow((218 + 6), 3) / 17 + 218) % 13))

print(hash_func(list_))

标签： pythonhashcollisiondoubly-linked-listhash-collision