设计ExtensibleHashTable类的随机测试程序，测试其中方法的正确性。

关注码龄粉丝数原力等级 -- 被采纳被点赞采纳率＄ 2024-04-17 20:12 采纳率: 90% 浏览 11 首页/ 数据结构与算法 / 已结题设计ExtensibleHashTable类的随机测试程序，测试其中方法的正确性。数据结构散列表设计ExtensibleHashTable类的随机测试程序，测试其中方法的正确性。 class Node : def __init__(self, data) -> None: self._data = data self.next: Node = None self.prior: Node = None def data(self): return self._data def __str__(self) -> str: return str(self._data) class LinkedList: def __init__(self): self._head = Node("head") self._head.next = self._head self._head.prior = self._head self._size = 0 def add(self, val): new_node = Node(val) self._head.next.prior = new_node new_node.next = self._head.next self._head.next = new_node new_node.prior = self._head self._size += 1 def remove(self, key): #if self.is_empty(): #return None p = self._head while p is not self._head.prior: p_data = p.next.data() if type(p_data) not in (tuple, list): p_data = [p_data] if p_data[0] == key: p.next.next.prior = p p.next = p.next.next self._size -= 1 return p_data[1] p = p.next return False def __getitem__(self, key): #if self.is_empty(): #raise Exception p = self._head res = None while p is not self._head.prior: p_data = p.next.data() if type(p_data) not in (tuple, list): p_data = [p_data] if p_data[0] == key: res = p_data[-1] break p = p.next return res def is_empty(self): return self.size() == 0 def size(self): return self._size def get_head(self): return self._head def front(self): return self._head.next.data() def __bool__(self): return self.is_empty() def __str__(self): res = [] t = self._head.next while t != self._head: res.append(str(t.data())) t = t.next return '[' + ' '.join(res) + f'], size: {self.size()}' class ExtensibleHashTable: def __init__(self, capacity=16, load_factor=2): # 桶（链表）的个数 self._capacity = capacity # 负载因子 self._load_factor = load_factor # 装着所有链表 self._buckets = [LinkedList() for _ in range(capacity)] # 当前的元素个数 self._size = 0 def __getitem__(self, key, defaultvalue=None): #"""实现table[key]的索引方式时间复杂度：O(k) 可以调用get方法""" return self.get(key,defaultvalue=None) def _resize(self): """当负载元素数量过多，则扩容""" new_table = ExtensibleHashTable(self._capacity * 2, load_factor=self._load_factor) for k, v in self.items(): new_table[k] = v self._size = new_table._size self._buckets = new_table._buckets self._capacity = new_table._capacity def __setitem__(self, key, value): if self._size / self._capacity > self._load_factor: # 如果哈希表的大小超过了负载因子乘以容量 self._resize() bucket=self.find_bucket(key) p = bucket._head while p is not bucket._head.prior: p_data = p.next.data() if type(p_data) not in (tuple, list): p_data = [p_data] if p_data[0] == key: p_data[-1]=value break p = p.next else: lst=[key,value] bucket.add(lst) self._size+=1 return # 如果负载过大，则_resize后添加 def find_bucket(self, key): index=self._hash_function(key) return self._buckets[index] # 返回buckets里面的某个链表 def is_empty(self): return self._size==0 def __iter__(self): for i in range(len(self._buckets)): bucket=self._buckets[i] p = bucket._head while p is not bucket._head.prior: p_data = p.next.data() yield p_data[0] p=p.next # 将每一个key值，通过 yield key 逐次生成 def _hash_function(self, key) -> int: return hash(key) % self._capacity #"""简易的哈希函数: 取余时间复杂度：O(1)""" def keys(self): return self.__iter__() def values(self): for i in range(len(self._buckets)): bucket=self._buckets[i] p = bucket._head while p is not bucket._head.prior: p_data = p.next.data() yield p_data[1] p=p.next # 将每一个value值，通过 yield value 逐次生成 def items(self): for i in range(len(self._buckets)): bucket=self._buckets[i] p = bucket._head while p is not bucket._head.prior: p_data = p.next.data() yield p_data[0],p_data[1] p=p.next # 将每一对key-value值，通过 yield key, value 逐次生成 def remove(self, key, defaultvalue=None): bucket=self.find_bucket(key) # 获取对应的桶的链表 if not bucket.is_empty(): # 如果桶不为空 value = bucket.remove(key) # 从桶中移除键对应的节点，并获取节点的数据 if value: # 如果获取到了数据 self._size -= 1 # 哈希表的大小减1 return value # 返回节点的值 if defaultvalue is None: # 如果没有设置默认值 raise KeyError(f"Key '{key}' not found") # 抛出KeyError异常 return defaultvalue # 如果设置了默认值，返回默认值 def get(self, key, defaultvalue=None): """获得key对应的value""" bucket=self.find_bucket(key) if not bucket.is_empty(): value=bucket.__getitem__(key) if value!=None: return value if defaultvalue is None: raise KeyError(f"Key '{key}' not found") return defaultvalue def size(self): return self._size 展开全部收起写回答好问题 0 提建议追加酬金关注问题微信扫一扫点击复制链接分享邀请回答编辑收藏删除收藏举报追加酬金 (90%的用户在追加酬金后获得了解决方案) 当前问题酬金 ¥ 0 (可追加 ¥500） ¥ 15¥ 20¥ 50¥ 100¥ 200 支付方式扫码支付二维码出错点击刷新支付金额 15 元提供问题酬金的用户不参与问题酬金结算和分配支付即为同意《付费问题酬金结算规则》结题再想想删除再等等

4条回答默认最新

专家-赤兔[在线] 全栈领域优质创作者 2024-04-17 20:12

关注

引自免费微信小程序：皆我百晓生

为了编写一个随机测试程序，我们将创建一个测试套件，用于测试ExtensibleHashTable类中的各种方法。这个测试套件将包括单元测试，确保每个方法按预期工作，以及一些压力测试，以检查在大量数据下的性能。

首先，我们需要导入必要的模块并定义一个测试类。然后，我们为每个方法编写测试用例。

import unittest
import random
from your_module import ExtensibleHashTable, Node, LinkedList

class TestExtensibleHashTable(unittest.TestCase):

    def setUp(self):
        self.table = ExtensibleHashTable(capacity=16, load_factor=2)

    def test_init(self):
        self.assertEqual(self.table.capacity, 16)
        self.assertEqual(self.table.load_factor, 2)
        self.assertEqual(self.table.size(), 0)

    def test_set_and_get(self):
        random_keys = [f'key_{i}' for i in range(10)]
        random_values = [f'value_{i}' for i in range(10)]

        for key, value in zip(random_keys, random_values):
            self.table[key] = value
            self.assertEqual(self.table.get(key), value)

    def test_resize(self):
        # Fill the table to trigger a resize
        random_keys = [f'key_{i}' for i in range(33)]
        for key in random_keys:
            self.table[key] = random.randint(1, 100)

        self.assertGreaterEqual(self.table.capacity, 32)
        self.assertEqual(self.table.size(), len(random_keys))

    def test_remove(self):
        random_keys = [f'key_{i}' for i in range(5)]
        random_values = [f'value_{i}' for i in range(5)]

        for key, value in zip(random_keys, random_values):
            self.table[key] = value
            self.assertIn(key, self.table.keys())
            del self.table[key]
            self.assertNotIn(key, self.table.keys())

    def test_default_value_on_missing_key(self):
        self.assertIsNone(self.table.get('non_existent_key', None))
        with self.assertRaises(KeyError):
            self.table['non_existent_key']

    def test_iterate(self):
        random_keys = [f'key_{i}' for i in range(7)]
        random_values = [f'value_{i}' for i in range(7)]

        for key, value in zip(random_keys, random_values):
            self.table[key] = value

        iterated_keys = set()
        for key in self.table:
            iterated_keys.add(key)
        self.assertEqual(iterated_keys, set(random_keys))

    def test_items(self):
        random_keys = [f'key_{i}' for i in range(8)]
        random_values = [f'value_{i}' for i in range(8)]

        for key, value in zip(random_keys, random_values):
            self.table[key] = value

        iterated_items = set()
        for item in self.table.items():
            iterated_items.add(item)
        expected_items = set(zip(random_keys, random_values))
        self.assertEqual(iterated_items, expected_items)

if __name__ == '__main__':
    unittest.main()

在这个测试类中，我们定义了一个名为TestExtensibleHashTable的子类，它继承了Python内置的unittest.TestCase类。我们使用setUp方法初始化一个ExtensibleHashTable实例，以便每个测试用例都可以访问到同一个测试对象。接下来，我们针对不同的功能编写了一系列测试方法，比如test_set_and_get、test_remove等。

要运行这些测试，只需执行上面的脚本即可。这将自动发现并运行所有的测试用例。如果有任何测试失败，unittest会提供详细的错误信息。

展开全部

本回答被题主选为最佳回答 , 对您是否有帮助呢? 本回答被专家选为最佳回答 , 对您是否有帮助呢? 本回答被题主和专家选为最佳回答 , 对您是否有帮助呢?