html成品网站,2024年还会封城吗,深圳设计周展会2023,安徽淮南了解HashMap原理对于日后的缓存机制多少有些认识。在网络中也有很多方面的帖子#xff0c;但是很多都是轻描淡写#xff0c;很少有把握的比较准确的信息#xff0c;在这里试着不妨说解一二。对于HashMap主要以键值(key-value)的方式来体现#xff0c;笼统的说就是采用key值…了解HashMap原理对于日后的缓存机制多少有些认识。在网络中也有很多方面的帖子但是很多都是轻描淡写很少有把握的比较准确的信息在这里试着不妨说解一二。对于HashMap主要以键值(key-value)的方式来体现笼统的说就是采用key值的哈希算法来外加取余最终获取索引而这个索引可以认定是一种地址既而把相应的value存储在地址指向内容中。这样说或许比较概念化也可能复述不够清楚来看列式更加清晰int hashkey.hashCode();//------------------------1int indexhash%table.lenth;//table表示当前对象的长度-----------------------2其实最终就是这两个式子决定了值得存储位置。但是以上两个表达式还有欠缺。为什么这么说例如在key.hashCode()后可能存在是一个负整数你会问是啊那这个时候怎么办呢所以在这里就需要进一步加强改造式子2了修改后的int index(hashOx7FFFFFFF)%table.lenth;到这里又迷惑了为什么上面是这样的呢对于先前我们谈到在hash有可能产生负数的情况这里我们使用当前的hash做一个“与”操作在这里需要和int最大的值相“与”。这样的话就可以保证数据的统一性把有符号的数值给“与”掉。而一般这里我们把二进制的数值转换成16进制的就变成了Ox7FFFFFFF。(注与操作的方式为不同为0相同为1)。而对于hashCode()的方法一般有public int hashCode(){int hash0,offset,lencount;char[] varvalue;for(int i0;ih31*hashvar[offset];}return hash;}说道这里大家可能会说到这里算完事了吧。但是你可曾想到如果数据都采用上面的方式最终得到的可能index会相同怎么办呢如果你想到的话那恭喜你!又增进一步了这里就是要说到一个名词冲突率。是的就是前面说道的一旦index有相同怎么办数据又该如何存放呢而且这个在数据量非常庞大的时候这个基率更大。这里按照算法需要明确的一点每个键(key)被散列分布到任何一个数组索引的可能性相同而且不取决于其它键分布的位置。这句话怎么理解呢从概率论的角度也就是说如果key的个数达到一个极限每个key分布的机率都是均等的。更进一步就是即便key1不等于key2也还是可能key1.hashCode()key2.hashCode()。对于早期的解决冲突的方法有折叠法(folding)例如我们在做系统的时候有时候会采用部门编号附加到某个单据标号后这里比如产生一个911位的编码。通过对半折叠做。现在的策略有1.键式散列2.开放地址法在了解这两个策略前我们先定义清楚几个名词解释threshold[阀值]对象大小的边界值;loadFactor[加载因子]n/m其中n代表对象元素个数m表示当前表的容积最大值threshold(int)table.length*loadFactor清晰了这几个定义我们再来看具体的解决方式键式散列我们直接看一个实例这样就更加清晰它的工作方式从而避免文字定义。我们这里还是来举一个图书编号的例子下面比如有这样一些编号78938-000045678-000172678-000224678-000116678-000198678-000385678-000245232-0004步骤1.把编号作为key,即int hashkey.hashCode();2.int indexhash%表大小3.逐步按顺序插入对象中现在问题出现了对于编号通过散列算法后很可能产生相同的索引值意味着存在冲突。解释上面的操作如果对于key.hashCode()产生了冲突(比如途中对于插入24678-0001对于通过哈希算法后可能产生的index或许也是501)既而把相应的前驱有相同的index的对象指向当前引用。这也就是大家认定的单链表方式。以此类推…而这里存在冲突对象的元素放在Entry对象中Entry具有以下一些属性int hash;Object key;Entry next;对于Entry对象就可以直接追溯到链表数据结构体中查阅。开放地址法1.线性地址探测法如何理解这个概念呢一句话就是通过算法规则在对象地址N1中查阅找到为NULL的索引内容。处理方式如果index索引与当前的index有冲突即把当前的索引index1。如果在index1已经存在占位现象(index1的内容不为NULL)试图接着index2执行。。。直到找到索引为内容为NULL的为止。这种处理方式也叫线性地址探测法(offset-of-1)如果采用线性地址探测法会带来一个效率的不良影响。现在我们来分析这种方式会带来哪些不良因素。大家试想下如果一个非常庞大的数据存储在Map中假如在某些记录集中有一些数据非常相似(他们产生的索引在内存的某个块中非常的密集)也就是说他们产生的索引地址是一个连续数值而造成数据成块现象。另一个致命的问题就是在数据删除后如果再次查询可能无法定到下一个连续数字这个又是一个什么概念呢例如以下图片就很好的说明开发地址散列如何把数据按照算法插入到对象中对于上图的注释步骤说明从数据“78938-0000”开始通过哈希算法按顺序依次插入到对象中例如78938-0000通过换算得到索引为0当前所指内容为NULL所以直接插入45678-0001同样通过换算得到索引为地址501所指内容当前内容为NULL所以也可以插入72678-0002得到索引502所指内容当前内容为NULL也可以插入请注意当24678-0001得到索引也为501当前地址所指内容为45678-0001。即表示当前数据存在冲突则直接对地址5011502所指向内容为72678-0002不为NULL也不允许插入再次对索引5021503所指内容为NULL允许插入。。。依次类推只要对于索引存在冲突现象则逐次下移位知道索引地址所指为NULL如果索引不冲突则还是按照算法放入内容。对于这样的对象是一种插入方式接下来就是我们的删除(remove)方法了。按照常理对于删除方式基本区别不大。但是现在问题又出现了如果删除的某个数据是一个存在冲突索引的内容带来后续的问题又会接踵而来。那是什么问题呢我们还是同样来看看图示的描述对于图-2中如果删除(remove)数据24678-0001的方法如下图所示对于我们会想当然的觉得只要把指向数据置为NULL就可以,这样的做法对于删除来说当然是没有问题的。如果再次定位检索数据16678-0001不会成功因为这个时候以前的链路已经堵上了但是需要检索的数据事实上又存在。那我们如何来解决这个问题呢对于JDK中的Entry类中的方法存在一个boolean markedForRemoval;它就是一个典型的删除标志位对于对象中如果需要删除时我们只是对于它做一个“软删除”即置一个标志位为true就可以。而插入时默认状态为false就可以。这样的话就变成以下图所示通过以上方式更好的解决冲突地址删除数据无法检索其他链路数据问题了。2.双散列(余商法)在了解开放地址散列的时候我们一直在说解决方法但是大家都知道一个数据结构的完善更多的是需要高效的算法。这当中我们却没有涉及到。接下来我们就来看看在开放地址散列中它存在的一些不足以及如何改善这样的方法既而达到无论是在方法的解决上还是在算法的复杂度上更加达到高效的方案。在图2-1中类似这样一些数据插入进对象存在冲突采用不断移位加一的方式直到找到不为NULL内容的索引地址。也正是由于这样一种可能加大了时间上的变慢。大家是否注意到像图这样一些数据目前呈现出一种连续索引的插入而且是一种成块是的数据。如果数据量非常的庞大或许这种可能性更大。尽管它解决了冲突但是对于数据检索的时间度来说我们是不敢想象的。所有分布到同一个索引index上的key保持相同的路径index,index1,index2…依此类推。更加糟糕的是索引键值的检索需要从索引开始查找。正是这样的原因对于线性探索法我们需要更进一步的改进。而刚才所描述这种成块出现的数据也就定义成簇。而这样一种现象称之为主簇现象。(主簇就是冲突处理允许簇加速增长时出现的现象)而开放式地址冲突也是允许主簇现象产生的。那我们如何来避免这种主簇现象呢这个方式就是我们要来说明的双散列解决冲突法了。主要的方式为uint hashkey.hasCode();uint index(hashOx7FFFFFFF)%table.length;u按照以上方式得到索引存在冲突则开始对当前索引移位而移位方式为ffset(hashOx7FFFFFFF)/table.length;u如果第一次移位还存在同样的冲突则继续当前冲突索引位置(索引号余数)%表.lengthu如果存在的余数恰好是表的倍数则作偏移位置为一下移依此类推这样双散列冲突处理就避免了主簇现象。至于HashSet的原理基本和它是一致的这里不再复述。在这里其实还是主要说了一些简单的解决方式而且都是在一些具体参数满足条件下的说明像一旦数据超过初始值该需要rehash加载因子一旦大于1.0是何种情况等等。还有很多问题都可以值得我们更加进一步讨论的比如在java.util.HashMap中的加载因子为什么会是0.75而它默认的初始大小为什么又是16等等这些问题都还值得说明。要说明这些问题可能又需要更加详尽的说明清楚。源码分析:HashMapHashMap是Java新Collection Framework中用来代替HashTable的一个实现HashMap和HashTable的区别是 HashMap是未经同步的而且允许null值。HashTable继承Dictionary而且使用了Enumeration所以被建议不要使用。HashMap的声明如下public class HashMap extends AbstractMap implements Map, Cloneable,Serializable有关AbstractMaphttp://blog.csdn.net/treeroot/archive/2004/09/20/110343.aspx有关Maphttp://blog.csdn.net/treeroot/archive/2004/09/20/110331.aspx有关Cloneablehttp://blog.csdn.net/treeroot/archive/2004/09/07/96936.aspx这个类比较复杂这里只是重点分析了几个方法特别是后面涉及到很多内部类都没有解释不过都比较简单。static final int DEFAULT_INITIAL_CAPACITY 16; 默认初始化大小static final int MAXIMUM_CAPACITY 1 30; 最大初始化大小static final float DEFAULT_LOAD_FACTOR 0.75f; 默认加载因子transient Entry[] table; 一个Entry类型的数组数组的长度为2的指数。transient int size; 映射的个数int threshold; 下一次扩容时的值final float loadFactor; 加载因子transient volatile int modCount; 修改次数public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);int capacity 1;while (capacity initialCapacity)capacity 1;this.loadFactor loadFactor;threshold (int)(capacity * loadFactor);table new Entry[capacity];init();}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR;threshold (int)(DEFAULT_INITIAL_CAPACITY);注意这里应该是一个失误 应该是threshold (int)(DEFAULT_INITIAL_CAPACITY * loadFactor);table new Entry[DEFAULT_INITIAL_CAPACITY];init();}public HashMap(Map m) {this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);putAllForCreate(m);}void init() {}static final Object NULL_KEY new Object();static Object maskNull(Object key){return (key null ? NULL_KEY : key);}static Object unmaskNull(Object key) {return (key NULL_KEY ? null : key);}static int hash(Object x) {int h x.hashCode();h ~(h 9);h ^ (h 14);h (h 4);h ^ (h 10);return h;}在HashTable中没有这个方法也就是说HashTable中是直接用对象的hashCode值但是HashMap做了改进 用这个算法来获得哈希值。static boolean eq(Object x, Object y) {return x y || x.equals(y);}static int indexFor(int h, int length) {return h (length-1);}根据哈希值和数组的长度来返回该hash值在数组中的位置只是简单的与关系。public int size() {return size;}public boolean isEmpty() {return size 0;}public Object get(Object key) {Object k maskNull(key);int hash hash(k);int i indexFor(hash, table.length);Entry e table[i];while (true) {if (e null) return e;if (e.hash hash eq(k, e.key)) return e.value;e e.next;}}这个方法是获取数据的方法首先获得哈希值这里把null值掩饰了并且hash值经过函数hash()修正。 然后计算该哈希值在数组中的索引值。如果该索引处的引用为null表示HashMap中不存在这个映射。 否则的话遍历整个链表这里找到了就返回,如果没有找到就遍历到链表末尾返回null。这里的比较是这样的e.hashhash eq(k,e.key) 也就是说如果hash不同就肯定认为不相等eq就被短路了只有在 hash相同的情况下才调用equals方法。现在我们该明白Object中说的如果两个对象equals返回true他们的 hashCode应该相同的道理了吧。假如两个对象调用equals返回true但是hashCode不一样那么在HashMap 里就认为他们不相等。public boolean containsKey(Object key) {Object k maskNull(key);int hash hash(k);int i indexFor(hash, table.length);Entry e table[i];while (e ! null) {if (e.hash hash eq(k, e.key)) return true;e e.next;}return false;}这个方法比上面的简单先找到哈希位置再遍历整个链表如果找到就返回true。Entry getEntry(Object key) {Object k maskNull(key);int hash hash(k);int i indexFor(hash, table.length);Entry e table[i];while (e ! null !(e.hash hash eq(k, e.key)))e e.next;return e;}这个方法根据key值返回Entry节点也是先获得索引位置再遍历链表如果没有找到返回的是null。public Object put(Object key, Object value) {Object k maskNull(key);int hash hash(k);int i indexFor(hash, table.length);for (Entry e table[i]; e ! null; e e.next) {if (e.hash hash eq(k, e.key)) {Object oldValue e.value;e.value value;e.recordAccess(this);return oldValue;}}modCount;addEntry(hash, k, value, i);return null;}首先获得hash索引位置如果该位置的引用为null那么直接插入一个映射返回null。如果此处的引用不是null必须遍历链表如果找到一个相同的key那么就更新该value同时返回原来的value值。如果遍历完了没有找到说明该key值不存在还是插入一个映射。如果hash值足够离散的话也就是说该索引没有被使用的话那么不不用遍历链表了。相反如果hash值不离散极端的说如果是常数的话所有的映射都会在这一个链表上效率会极其低下。这里举一个最简单的例子写两个不同的类作为key插入到HashMap中效率会远远不同。class Good{int i;public Good(int i){this.ii;}public boolean equals(Object o){return (o instanceof Good) (this.i((Good)o).i)}public int hashCode(){return i;}}class Bad{int i;public Good(int i){this.ii;}public boolean equals(Object o){return (o instanceof Good) (this.i((Good)o).i)posted on 2009-05-14 13:32 郭鹏 阅读(791) 评论(0) 编辑 收藏 所属分类: JAVA
