不允许你还没有了解哈希表、哈希桶、哈希冲突的解决，如何避免冲突 |
您所在的位置：网站首页 › 线性hash表的冲突次数怎么数 › 不允许你还没有了解哈希表、哈希桶、哈希冲突的解决，如何避免冲突 |
不允许你还没有了解哈希表、哈希桶、哈希冲突的解决，如何避免冲突
|
✏️✏️✏️今天给各位带来的是哈希桶、哈希冲突方面的知识。 清风的CSDN博客 😛😛😛希望我的文章能对你有所帮助，有不足的地方还请各位看官多多指教，大家一起学习交流！ 动动你们发财的小手，点点关注点点赞！在此谢过啦！哈哈哈！😛😛😛
目录 一、哈希表 1.1 概念 1.2 冲突 1.2.1 冲突概念 1.2.2 冲突避免 1.2.3 冲突避免-哈希函数设计 1.2.4 负载因子调节 1.2.5 冲突解决-闭散列 1.2.6 冲突解决-开散列 1.2.7 哈希桶K-V型实现 1.3 性能分析 一、哈希表 1.1 概念 顺序结构以及平衡树 中，元素关键码与其存储位置之间没有对应的关系，因此在 查找一个元素时，必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N), 平衡树中为树的高度，即 O(当向该结构中： 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。 该方式即为 哈希(散列) 方法， 哈希方法中使用的转换函数称为哈希 ( 散列 ) 函数，构造出来的结构称为哈希表 (Hash Table)( 或者称散列表 ) 例如：数据集合 {1 ， 7 ， 6 ， 4 ， 5 ， 9} ； 哈希函数设置为： hash(key) = key % capacity ; capacity 为存储元素底层空间总的大小。
常见哈希函数： 直接定制法--(常用) 取关键字的某个线性函数为散列地址： Hash （ Key ） = A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况。 除留余数法--(常用) 设散列表中允许的 地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数： Hash(key) = key% p(pDEFAULT_LOAD_FACTOR){ resize(); } } //计算当前负载因子 private float doLOAD_FACTOR(){ return usedSize*1.0f / array.length; } //如果哈希桶已满，扩容后重新哈希 private void resize(){ Node[] newArray = new Node[array.length*2]; for (int i = 0; i < array.length; i++) { Node cur = array[i]; while (cur!=null){ //先生成整数，调用hashCode Node curNext = cur.next; int newHash = cur.key.hashCode(); int newIndex = newHash % newArray.length; cur.next = newArray[newIndex]; cur = curNext; } } array = newArray; }获取key位置的val值： public V getValue(K key){ int hash = key.hashCode(); int index = hash % array.length; Node cur = array[index]; while (cur!=null){ if(cur.key.equals(key)){//引用类型不可使用等号比较!!!!!! return cur.val; } cur = cur.next; } return null; } 1.3 性能分析 虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入 / 删除 / 查找时间复杂度是 O(1) 。✨希望各位看官读完文章后，能够有所提升。 🎉好啦，今天的分享就到这里！！ ✨创作不易，还希望各位大佬支持一下！ 👍点赞，你的认可是我创作的动力！ ⭐收藏，你的青睐是我努力的方向！ ✏️评论：你的意见是我进步的财富！
|
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |