散列是什么? 例如,我有原始值。 s=“双击老铁666”、“感谢老铁送来的飞机”、
用java的hasecode (取得变量的物理地址)等某种算法得到的666就是“散列码”)字符串。”
然后,通过“散列算法”“取馀数法等”得到的值例如为1,该1为“散列值”,将“散列值”作为数组的下标,将与该下标对应的位置作为键值对的存储位置这些关系的东西就是哈希表。
说明:以上的剩余运算为666%N。 n在下图的意义上是3。 通常为计数(s )/5。 太长会产生很多空项,太短会导致很多值长链搜索
散列冲突是什么? 1 .拉链法:
上图为什么1的位置后面有两个数据呢? 因为其他值经过散列运算得到的散列值也可能为1。 这就是散列碰撞(散列碰撞)。 解决方法有很多。 链地址法适用于频繁插入和删除的情况。
2 .开放地址法:开放地址法分为线性检测法和双重哈希法
(图为线性检测法)
线性检测方法假设元素29的散列运算后也为29
插入元素29 :元素29的哈希值为29,29=1,但第一个元素已经有数值15。 接下来检查下一个元素(2号元素),2号元素已经有数值30。 接下来是下一个元素) 3号元素)。 3号元素是空的,插入3号元素中
元素29 )元素29哈希值为29,29=1,检查元素1号,15!=29; 然后检查下一个元素(2号元素),30!=29; 然后检查以下元素(3号元素),29=29,返回数值,搜索完成。
双重散列法也称为重新散列法,除了重新散列函数之外,还准备了另一个散列函数2。 地址冲突时,执行函数2,冲突时,将函数2得到的值加1,加2直到不冲突。
摘要hash table哈希表是一种基于数组的存储方法,存储上有一对键值(用于存储密钥、值的集合)数组。 保存数据时,首先使用函数计算数据的地址,然后将数据保存到指定地址位置的数组中。 此函数是散列函数,此数组是哈希表。 哈希的主要应用是哈希表和分布式缓存。
注:请总结自己的理解,如果有错误请在信息中指出。