数据结构:哈希表

实验 3.1 - 哈希表HashTable

具有链寻址的可扩展的哈希表

在本实验中，您将构建一个哈希表实现，该实现使用链地址来解决冲突，并且如果哈希表的填充因子超过给定阈值，则会自动增加哈希表大小。

一旦哈希表超过 loadfactor 满，你应该重建它，将桶的数量加倍。

例如，如果您有一个带有填充因子“0.5”和“100”桶的哈希表，那么一旦它存储超过“0.5 * 100 = 50”个元素，就需要使用“200”桶重新构建它。

您应该实现下面显示的所有方法。

方法实现（70分）

关于您需要完成的方法的一些说明：

• is_empty(self) - 判断self是否为空HashTable。
  

  
  

• __getitem__(self, key, defaultvalue=None) - 返回self[key]。
  

  
  

  如果哈希表中不存在key，返回defaultvalue。
  

  
  

  如果哈希表中不存在key并且defaultvalue没有被赋其他值，需要引发KeyError。
  

  
  

• __setitem__(self, key, value) - 如果key存在，将self[key]设置为 value，否则加入一个新的键值对。
  

  
  

• find_bucket(self, key) - 返回self[key]存储在哈希表的桶号。
  

  
  

• remove(self, key, defaultvalue=None) - 删除self[key]，并返回对应的值。
  

  
  

  如果哈希表中不存在key，则返回defaultvalue。
  

  
  

  如果哈希表中不存在key并且defaultvalue 没有被赋其他值，需要引发KeyError。
  

  
  

• __iter__(self) - 返回哈希表中键的迭代器。
  

  
  

• values(self) - 应该是一个生成器，返回self中value的迭代器。
  

  
  

• items(self) - 应该是一个生成器，将哈希表的数据项作为元组 (key,value)，返回self中数据项的迭代器。
  

  
  

测试 （30分）

正确性测试：设计单元测试用例，测试HashTable的 *** 作功能的正确性。

性能测试：设计性能测试方案，测试HashTable查找成功的平均关键字比较次数以及查找不成功的平均关键字比较次数。

代码

引用上一帖中的链队列(LinkedQueue)部分代码

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

class LinkedQueue(object):
    def __init__(self):
        temp_node = Node(None)
        self.front = temp_node
        self.rear = temp_node

    def LinkQueue(self, val_list):
        for val in val_list:
            self.enqueue(val)

    def isEmpty(self):
        if self.front == self.rear:
            return True
        else:
            return False

    def size(self):
        prehead = self.front
        count = 0
        while prehead.next:
            count += 1
            prehead = prehead.next
        return count

    def enqueue(self, e):
        new_node = Node(e)
        if self.isEmpty():
            self.front.next = new_node
        self.rear.next = new_node
        self.rear = self.rear.next

    def dequeue(self):
        if self.isEmpty():
            print('队为空!')
            exit()
        else:
            temp = self.front.next
            self.front.next = temp.next
            if self.rear == temp:
                # 这个结点是尾结点
                self.front = self.rear
            return temp.data

    def get_head(self):
        return self.front.next.data

from LinkQueue import *

def hash(astring, tablesize):
    sum = 0
    for pos in range(len(astring)):
        sum = sum + ord(astring[pos])

    return sum % tablesize

class HashTable:
    def __init__(self):
        self.load_factor = 0.5
        self.size = 100
        self.slots = [None] * self.size
        self.data = [None] * self.size
        self.data_num = 0

    def put(self, key, data):
        hashvalue = self.hashfunction(key, len(self.slots))

        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = LinkedQueue()
            self.data[hashvalue].enqueue(data)
            self.data_num += 1
        else:
            self.slots[hashvalue] = key
            self.data[hashvalue].enqueue(data)
            self.data_num += 1

    def hashfunction(self, key, size):
        return key % size

    def get(self, key):
        startslot = self.hashfunction(key, len(self.slots))

        data = None
        stop = False
        found = False
        position = startslot

        while self.slots[position] != None and \
                not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position].get_head()
            else:
                # 待处理(在该链表中搜索)
                position = self.rehash(position, len(self.slots))
                if position == startslot:
                    stop = True
        return data

    def is_empty(self):
        if self.data_num == 0:
            return True
        else:
            return False

    def find_bucket(self, key):
        size = self.size
        return self.hashfunction(key, size)

    def remove(self, key, defaultvalue=None):
        return 0

    def values(self):
        return 0

    def items(self):
        return 0

    def __getitem__(self, key, defaultvalue=None):
        item = self.get(key)
        if item == defaultvalue:
            # raise Exception("KeyError:this key not exit in HashTable")
            return defaultvalue

        else:
            return item

    def __setitem__(self, key, data):
        self.put(key, data)

    def __len__(self):
        return self.data_num

    def __iter__(self):
        return 0