Java HashMap深度认识
发布时间：2021-11-24 13:50:29 所属栏目：教程 来源：互联网
导读：根据云计算网_泰州站长网 Www.0523Zz.Com报道 一、首先再简单重复一下Hash算法 简单的说就是一种将任意内容的输入转换成相同长度输出（有个范围，假设10位的数字，用一个称之为HashTable的容器来存放）的加密方式------hash 如（假设）： a---10位数1 123---1
|
根据云计算网_泰州站长网 Www.0523Zz.Com报道 一、首先再简单重复一下Hash算法 简单的说就是一种将任意内容的输入转换成相同长度输出（有个范围，假设10位的数字，用一个称之为HashTable的容器来存放）的加密方式------hash 如（假设）： “a”---à10位数1 123---à10位数2 … 注意：任意内容的输入，范围是无穷无尽，肯定比相同长度输出（如10位数）要大很多，那么就会造成不同的输入，会得到相同的输出（值）----hash冲突 HashMap当然也无法避免冲突问题 二、HashMap源码片段 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR;//负载因子，默认0.75 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; //使用的是Entry数组 init(); } public V put(K key, V value) { if (key == null)//空的情况，允许存空 return putForNullKey(value); int hash = hash(key.hashCode());//根据key的hashCode再来计算一个hash值----根据hash冲突可以知道不同的key对应的hashCode可能一样（如果不被重写的话，Object的hashCode()生成的hashCode存放在Java底层的一个大的HashTable上，不过我想JDK应该已经做过冲突处理，不会使用这么简单的hash算法，除非自己重写hashCode(),否则应该不会有冲突，真的发生冲突估计要内存溢出了） //就算hashCode不同，通过hash()出来的hash值也可能冲突(后面会讲到) int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//该位置已经有了，且key也完全是同一个，就覆盖，否则也是走下面的新开(后面会有例子) V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }//已经存在的情况 //以下是新增的情况 modCount++; addEntry(hash, key, value, i); return null; } /** 为给定的hashCode增加一个hash方法，用于抵消低质量的hash函数。这是很关键的，因为HashMap使用power-of-two长度的hash表，否则遇到冲突的hashCode无法区分 */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } //根据hashCode及table的长度计算index static int indexFor(int h, int length) { return h & (length-1); } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex];//先取原有的元素作为next，index冲突的时候用，形成一个“链条” table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next;//存放自己的下一个 final int hash; ... } //------再看一下get方法 public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //根据key的hashCode计算出“链条”在table中的index，再到“链条”中查找符合自己key的对象 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }  （编辑：三明站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐