专栏首页lgp20151222hash冲突解决和javahash冲突解决

hash冲突解决和javahash冲突解决

其实就是四种方法的演变

1.开放定址法

具体就是把数据的标志等的对长度取模

有三种不同的取模

线性探测再散列 给数据的标志加增量,取模

平方探测再散列 给数据的标志平方,取模

随机探测再散列 把数据的标志随机化,取模

线性,平方显然很容被人猜出规律,所以最终是随机,那么是不是存在随机会出现取模的值相等的情况?

2.链地址法

而解决值不同,hash相同的方法有链地址法。

//先从数组上取下原来的值,给塞到新的节点去,然后把新的节点再放到数组上。  
void createEntry(int hash, K key, V value, int bucketIndex) {  
       Entry<K,V> e = table[bucketIndex];  
       table[bucketIndex] = new Entry<>(hash, key, value, e);  
       size++;  
} 
Entry(int h, K k, V v, Entry<K,V> n) {  
          value = v;  
          next = n;  
          key = k;  
          hash = h;  
}  

将值不同hash相同的放在同一个地方,取值时遍历数据。

那么是不是存在一个地方有几个值,一个地方没有值的情况?

3.再hash法

就是当hash遇到重复的hash的时候,给自己在hash一次,然后hashCount+1,说明要多hash一次获取地址。

那么是不是存在hashCount+9999999,才能找到地址的情况?

4.建立一个公共溢出区

上面都有hashCount来记录hash的次数了,我直接新一个公共溢出区,用overIndex=99来记录不是更好吗?

那么,hash冲突基本解决,但是同样存在一个问题!

建立一个公共溢出区在map容器小的时候,作用不大,放在公共溢出区还不如扩容。只有当map的容器越大,扩容需要的空间越多,公共溢出区才实用。

5.java的hash冲突解决 链地址法

put方法分析

    public V put(K key, V value) {
        //hash()方法在上面已经出现过了,就不贴了
        return putVal(hash(key), key, value, false, true);
    }
 
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;
        // tab为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 计算index,并对null做处理
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K, V> e;
            K k;
            // 节点key存在,直接覆盖value
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                // 判断该链为红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                // 该链为链表
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于8转换为红黑树进行处理 TREEIFY_THRESHOLD = 8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // key已经存在并相等,不往链表加值
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
             // key不存在,p,e是老值,p.next是新值
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
           //链地址法触发,返回老值,写了这么久代码才知道put返回不仅仅是null。
                return oldValue;
            }
        }
        ++modCount;
        // 超过最大容量 就扩容  threshold:单词解释--阈(yu)值,不念阀(fa)值!顺便学下语文咯。
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RestTemplate的异常:Not enough variables available to expand

    原因:RestTemplate使用出错,我的情况是不知道这里要求用RestTemplate的使用格式,应该很多人都是这样吧?不过,看了下RestTemplate...

    ydymz
  • mysql连接error,Establishing SSL connection without server's identity verification is not recommended.

    Establishing SSL connection without server's identity verification is not recomm...

    ydymz
  • Redis设置Key的过期时间 – EXPIRE命令

    为给定 key 设置生存时间,当 key 过期时(生存时间为 0 ),它会被自动删除。

    ydymz
  • BAT面试必问HashMap源码分析

    HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。

    美的让人心动
  • 程序猿的日常——HashMap的相关知识

    背景知识 ? 哈希冲突 哈希是指通过某种方法把数据转变成特定的数值,数值根据mod对应到不同的单元上。比如在Java中,字符串就是通过每个字符的编码来计算、数字...

    用户1154259
  • Java HashMap工作原理及实现(干货)

    发生了什么呢?下面是一个大致的结构,希望我们对HashMap的结构有一个感性的认识:

    用户1257215
  • HashMap中add()方法的源码学习

    HashMap中实际是维护了一个Node数组,用来存储数据,下面看一下Node源码:

    会说话的丶猫
  • JDK容器学习之HashMap (一) : 底层存储结构分析

    底层数据结构 首先通过源码,类中的field如下, transient Node<K,V>[] table; transient Set<Map.Entry<...

    一灰灰blog
  • HashMap源码

    在put源码中,且有一段循环遍历就是为了防止存在相同的 key 值,若发现两个 hash 值(key)相同时,HashMap 的处理方式是用新 value 替换...

    小土豆Yuki
  • Java内功系列-HashSet是如何保证元素不重复的

    我们都知道HashSet存放的元素是不允许重复的,那么HashSet又是是如何保证元素不可重复的,你知道吗?

    一个程序员的成长

扫码关注云+社区

领取腾讯云代金券