HashMap hash Methods

2010-07-10  来源:本站原创  分类:Java  人气:145 

HashMap in the hash table location algorithm:

int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);

One indexFor and hash source as follows:

/**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    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);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

indexFor forum this method has been analyzed, there is no longer analysis.
Now analysis of hash algorithms:

h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);

Suppose key.hashCode () value: 0x7FFFFFFF, table.length to the default value of 16.
The implementation of the above algorithm is as follows:

HashMap hash Methods

Be i = 15

Among
h ^ (h>>> 7) ^ (h>>> 4) results in the bit run identification is to h>>> 7 replaced by h>>> 8 run.

Final h ^ (h>>> 8) ^ (h>>> 4) After computing the value of each hashCode values are as follows:
8 = 8
7 = 7 ^ 8
6 = 6 ^ 7 ^ 8
5 = 5 ^ 8 ^ 7 ^ 6
4 = 4 ^ 7 ^ 6 ^ 5 ^ 8
3 = 3 ^ 8 ^ 6 ^ 5 ^ 8 ^ 4 ^ 7
2 = 2 ^ 7 ^ 5 ^ 4 ^ 7 ^ 3 ^ 8 ^ 6
1 = 1 ^ 6 ^ 4 ^ 3 ^ 8 ^ 6 ^ 2 ^ 7 ^ 5
Results in duplication of 2,3-two-bit computing ^
3 = 3 ^ 8 ^ 6 ^ 5 ^ 8 ^ 4 ^ 7 -> 3 ^ 6 ^ 5 ^ 4 ^ 7
2 = 2 ^ 7 ^ 5 ^ 4 ^ 7 ^ 3 ^ 8 ^ 6 -> 2 ^ 5 ^ 4 ^ 3 ^ 8 ^ 6
Uehara hashCode lowest of eight are involved in the ^ operator, so table.length the case for the default values of 16 below, hashCode any position changes can be reflected in the final hash table positioning algorithm.

Algorithm is used (h>>> 7) rather than (h>>> 8) of the algorithm, I do not know whether it is considered a duplication of the two-bit ^ 2,3 computing situation.
Use (h>>> 7) If the default value of 16 in table.length where the first three original hashCode high a change will not respond to the results, namely: 0x7FFFF7FF of i = 15.

相关文章
  • HashMap hash Methods 2010-07-10

    HashMap in the hash table location algorithm: int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); One indexFor and hash source as follows: /** * Applies a supplemental hash function to a given hashCode, which * defends against poor

  • java in the hashmap and hashtable (2) 2009-06-24

    java in the hashmap and hashtable (2) - Beginner's Guide 2009-02-10 13:37 Hashtables provides a useful way to make optimum application performance. Hashtables (hash table) in the computer field is not a new concept. They are used to speed up the comp

  • The difference between Hashtable and HashMap 2010-03-30

    1.Hashtable is a subclass of Dictionary, HashMap is an implementation of Map interface class; 2.Hashtable the method is synchronized, and the method of HashMap by default non-synchronous. In other words, in multi-threaded applications, not specifical

  • hashTable difference with HashMap 2010-04-19

    hashTable difference with HashMap Reprinted from: http://blog.sina.com.cn/s/blog_4cdde9680100folj.html HashTable is widely used, HashMap is new framework to replace the HashTable class, that recommend the use of HashMap, do not use HashTable. Perhaps

  • Another difference between hashtable and hashmap 2010-06-17

    Hashtable and HashMap class has three important differences. The first difference is mainly for historical reasons. Hashtable is based on the old Dictionary class, HashMap is Java 1.2 introduced an implementation of Map interface. Perhaps the most im

  • HashMap v.s. HashTable 2010-06-27

    http://www.cnblogs.com/taotaoblog/archive/2009/09/19/1569958.html http://hi.baidu.com/% CE% D2% D7% D4% CE% DE% BB% DA/blog/item/5ba64f90a68dab8aa877a45a.html 1, inheritance, and to achieve distinction Dictionary Hashtable class is based on the old c

  • Android ArrayList LinkedList Set HashMap introduction. 2010-10-11

    In the Android development, we often need for data classification and operation of data storage for the lightweight SQLite or we may not need to use efficiency, and inadequate library XML, data not available due SharedPreferences enumeration method,

  • java HashMap implementation principle [Z] 2010-10-12

    In-depth collection of Java Learning Series: HashMap implementation principle 1. HashMap Overview: HashMap Hash table based on asynchronous Map interface implementation. This implementation provides all optional map operations, and allows the use of

  • In-depth collection of Java Learning Series: HashMap implementation principle (to) 2010-10-29

    In-depth collection of Java Learning Series: HashMap implementation principle Articles Category: Java Programming 1. HashMap Overview: HashMap Hash table based on asynchronous Map interface implementation. This implementation provides all optional ma

  • Hash table analysis and the Java implementation 2010-11-29

    This blog focuses on some of the principles Hash table / concept, and in accordance with these principles / concepts, one for storage of their own design / Hash table to find data, and with the JDK's HashMap class comparison. We look at seven steps t

  • With regard to the collection hashtable, hashmap, hashset, treemap, treeset Some simple experience 2010-03-29

    Hashtable Is a subclass of Dictionary, HashMap is an implementation of Map interface, the application of a very broad class HashTable, HashMap is a new framework to replace the HashTable class, that recommend the use of HashMap, do not use HashTable.

  • hashTable and hashMap 2010-04-17

    1: hashTable does not allow null values, either key or value, hashmap is allowed 2: hashmap iterate traversal is to use 3: HashTable have a contains (Object value) 4: HashTable in the hash array size is 11 by default to old * 2 +1 way to add value. H

  • The difference between HashMap and Hashtable (rpm) 2010-10-05

    Is widely used HashTable, HashMap is a new framework to replace the HashTable class, that recommend the use of HashMap, do not use HashTable. Perhaps you feel that HashTable is useful, why not? This simple analysis of their differences. 1.HashTable m

  • The difference between Hashtable and HashMap classes 2010-10-21

    Hashtable and HashMap class has three important differences. The first difference is mainly for historical reasons. Dictionary Hashtable is a class based on the old, HashMap is a Java 1.2 introduced an implementation of Map interface.     Perhaps

  • HashMap Hashtable LinkedHashMap TreeMap WeakHashMap and ConcurrentMap difference 2011-04-19

    HashMap Hashtable LinkedHashMap TreeMap WeakHashMap and ConcurrentMap difference java mapping for data structure defines an interface java.util.Map; it has four implementation classes are HashMap Hashtable LinkedHashMap and TreeMap. Map key is used t

  • java数据结构-HashMap 2013-03-19

    Map和Collection在结构层次上是没有任何关系的,通过查看源码可以发现map所有操作都是基于key-value对,而不是单独的元素. 下面以HashMap为例子,深入对Map的实现机制进行了解,在这个过程中,请打开jdk源码. Hash算法 HashMap使用Hash算法,所以在解剖HashMap之间,需要先简单的了解Hash算法,Hash算法一般也成为散列算法,通过散列算法将任意的值转化成固定的长度输出,该输出就是散列值,这是一种压缩映射,也就是,散列值的空间远远小于输入的值空间. 简

  • JAVA utils Collection array list 2010-04-11

    1, Iterator (an important interface) Is a unified approach to traverse the elements of the various collections / iteration tools, also known as "iterator." It allows the "traverse" the process of removing the elements of the collection

  • List Set ArrayList difference Xiangjie 2010-04-14

    List is a list of (interface), it can allow duplicate values, Set is a collection does not allow duplicate values ArrayList (General Category) list interfaces to achieve arraylist and vector is similar, but is not synchronized arraylist vector ArrayL

  • UF out to interview a few questions pavement 2010-06-24

    1.Hashtable and HashMap What is the difference? 2. How do you understand the MVC pattern? 3.SQLServer left join query with left join, Oracle using what? 4.SQLServer in the database, Oracle corresponding to? 5. If there are two databases in SQLServer,

  • Source with the mind 2010-09-04

    Recent studies of the source code under the struts2.2.1 bottom see many sets of applications, realize their own understanding of Set and Map is not in place, what Set, Entry of the class of all Sha Sha Sha Well, Well, the book opened fill up classes,