首页 > 试题广场 >

设散列表的长度为10,散列函数H(n)=n mod 7,初始

[单选题]
设散列表的长度为10,散列函数H(n)=n mod 7,初始关键字序列为 (33,24,8,17,21,10),用链地址法作为解决冲突的方法,平均查找长度是?
  • 1
  • 1.5
  • 2
  • 2.5
hashmap的构造方式的一种,就是构造一个长度为7的数组(哈希函数的除数), 把每个余数相同的数去对应的数组元素里面去找,数组存放的是链表,遍历链表,如果当前指针指向的元素与查找的元素相同就返回,如果找不到,就在最后添加上这个元素。
33%7=5->1 (数组元素是空链表,直接添加元素,比较次数是1)
24%7=3->1
8%7=1->1
17%7=3->2(在构造数组的nums[2],之前已经存储了一个3(在24%7),所以需要比较两次)
21%7=0->1
10%7=3->3
res = (1+1+1+2+1+3)/6=1.5
我是按照leetcode上面一道构造hashmap的题目来说的,不知道对不对,欢迎指点。
发表于 2019-12-02 15:21:03 回复(1)
33/7=5, 查找33需要1次;
24/7=3,查找24需要1次;
8/7=1,查找8需要1次;
17/7=3,查找17需要2次;
21/7=0,查找21需要1次;
10/7=3,查找10需要3次;
ASL=每个关键字查找的次数之和/关键字的个数=(1+1+1+2+3+1)/6=1.5
发表于 2019-09-05 09:56:26 回复(3)
哈希表不考虑冲突查找的时间复杂度是O(1),而考虑冲突就是取决于使用解决冲突的方式,如果是链地址解决冲突的话,时间复杂度是n/2。如果是红黑树的话,就是log2(n)。这里的散列后3号数组有3个链表节点,所以时间复杂度是3/2=1.5。
发表于 2020-04-02 21:16:53 回复(0)
hashmap的构造方式的一种,就是构造一个长度为7的数组(哈希函数的除数), 把每个余数相同的数去对应的数组元素里面去找,数组存放的是链表,遍历链表,如果当前指针指向的元素与查找的元素相同就返回,如果找不到,就在最后添加上这个元素。
33%7=5->1 (数组元素是空链表,直接添加元素,比较次数是1)
24%7=3->1
8%7=1->1
17%7=3->2(在构造数组的nums[2],之前已经存储了一个3(在24%7),所以需要比较两次)
21%7=0->1
10%7=3->3
res = (1+1+1+2+1+3)/6=1.5
我是按照leetcode上面一道构造hashmap的题目来说的,不知道对不对,欢迎指点。
发表于 2021-06-03 13:13:18 回复(0)
主要模,可能存在碰撞回增加次数,再除以要查找的总数,取平均
发表于 2022-04-13 11:02:14 回复(0)
相同余数多出现一次,查找多一次;数据10包括自己在内有三个余数“3”,则需要找到10需要查找3次
发表于 2023-08-01 15:05:57 回复(0)
10除7余数写成2😂
发表于 2023-06-13 11:48:34 回复(0)
那这个长度为10是无用条件吗
发表于 2021-12-21 00:04:05 回复(1)