关于Java中的HashMap实现 [英] Regarding HashMap implementation in java

问题描述

我试图对hashmap进行研究，并提出以下分析：

http://stackoverflow.com/questions/11596549/how-does-javas-hashmap-work-internally/18492835#18492835

Q1你能告诉我一个简单的地图，你可以显示过程...如何使用这个公式详细计算给定键的哈希码。计算位置哈希％（arrayLength-1））其中元素应放置（桶号），假设我有这个hashMap

  = new HashMap（）; // HashMap关键字随机顺序。 
 map.put（Amit，Java）; 
 map.put（Saral，J2EE）; 
  

Q2有时候，可能会发生两个不同对象的hashCodes是相同的。在这种情况下，2个对象将被保存在一个桶中，并将显示为LinkedList。入口点是最近添加的对象。这个对象引用其他objest有下一个字段，所以一个。最后一个条目是指null。你可以用真实的例子给我看看。

。

Amit到第10桶，因为位twiddeling。如果没有位twiddeling它会去第7桶，因为2044535&

更新的快照...

p>

image is ...

解决方案

使用
详细计算给定键的哈希码公式

如果 String ，则计算方式为 String＃hashCode（）; 其实现如下：

  public int hashCode 
 int h = hash; 
 int len = count; 
 if（h == 0& len> 0）{
 int off = offset; 
 char val [] = value; 
 
 for（int i = 0; i  h = 31 * h + val [off ++]; 
} 
 hash = h; 
} 
 return h; 
} 
  

基本上遵循java doc中的公式

  hashcode = s [0] * 31 ^（n-1）+ s [1] * 31 ^（n-2） n-1] 
  

这个实现的一个有趣的事情是 String 实际缓存其哈希码。它可以这样做，因为 String 是不可变的。

如果我计算 String Amit，它将产生此整数：

  System.out.println Amit.hashCode（））; 
> 2044535 
  

让我们通过一个简单的放置到地图，但首先我们必须确定地图如何建造。
关于Java HashMap 最有趣的事实是它总是有2 ^ n个桶。所以如果你调用它，默认的桶数是16，这显然是2 ^ 4。

在此地图上执行put操作，它将首先获取密钥的哈希码。在这个哈希码上发生了一些奇怪的位，以确保差的哈希函数（特别是那些在低位没有区别的哈希函数）不会超载单个桶。

实际上负责将密钥分配到存储分区的真正功能如下：

  h& （长度-1）。 // length是当前的桶数，h是密钥的哈希码
  

的两个桶尺寸，因为它使用&将密钥映射到桶而不是模。

Amit将被分发到第10个桶，因为位twiddeling。如果没有位twiddeling它会去第七桶，因为 2044535& 15 = 7 。

现在我们有一个索引，我们可以找到桶。如果桶包含元素，我们必须迭代它们，并替换一个相等的条目，如果我们找到它。
如果在链接列表中找不到任何项目，我们只需将它添加到链接列表的开头。

<$ c下的重要事项$ c> HashMap 是调整大小，因此如果地图的实际大小超过阈值（由当前的桶数和负载因子（在我们的例子中为16 * 0.75 = 12）确定）将调整背衬阵列的大小。
Resize总是2 *当前桶的数量，这是一个二的幂，不打破功能找到桶。

由于桶的数量变化，我们必须重新清除我们表中的所有当前条目。
这是相当昂贵的，所以如果你知道有多少项目，你应该用该计数初始化 HashMap ，所以它不必调整整个时间。

I was trying to do research on hashmap and came up with the following analysis:

http://stackoverflow.com/questions/11596549/how-does-javas-hashmap-work-internally/18492835#18492835

Q1 Can you guys show me a simple map where you can show the process..that how hashcode for the given key is calculated in detail by using this formula ..Calculate position hash % (arrayLength-1)) where element should be placed(bucket number), let say I have this hashMap

HashMap map=new HashMap();//HashMap key random order.
         map.put("Amit","Java");
         map.put("Saral","J2EE");

Q2 Sometimes it might happen that hashCodes for 2 different objects are the same. In this case 2 objects will be saved in one bucket and will be presented as LinkedList. The entry point is more recently added object. This object refers to other objest with next field and so one. Last entry refers to null. Can you guys show me this with real example..!!

.

"Amit" will be distributed to the 10th bucket, because of the bit twiddeling. If there were no bit twiddeling it would go to the 7th bucket, because 2044535 & 15 = 7. how this is possible please explanin detail the whole calculation..?

Snapshots updated...

and the other image is ...

解决方案

that how hashcode for the given key is calculated in detail by using this formula

In case of String this is calculated by String#hashCode(); which is implemented as follows:

 public int hashCode() {
    int h = hash;
        int len = count;
    if (h == 0 && len > 0) {
        int off = offset;
        char val[] = value;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

Basically following the equation in the java doc

 hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

One interesting thing to note on this implementation is that String actually caches its hash code. It can do this, because String is immutable.

If I calculate the hashcode of the String "Amit", it will yield to this integer:

System.out.println("Amit".hashCode());
>     2044535

Let's get through a simple put to a map, but first we have to determine how the map is built. The most interesting fact about a Java HashMap is that it always has 2^n buckets. So if you call it, the default number of buckets is 16, which is obviously 2^4.

Doing a put operation on this map, it will first get the hashcode of the key. There happens some fancy bit twiddeling on this hashcode to ensure that poor hash functions (especially those that do not differ in the lower bits) don't "overload" a single bucket.

The real function that is actually responsible for distributing your key to the buckets is the following:

 h & (length-1); // length is the current number of buckets, h the hashcode of the key

This only works for power of two bucket sizes, because it uses & to map the key to a bucket instead of a modulo.

"Amit" will be distributed to the 10th bucket, because of the bit twiddeling. If there were no bit twiddeling it would go to the 7th bucket, because 2044535 & 15 = 7.

Now that we have an index for it, we can find the bucket. If the bucket contains elements, we have to iterate over them and replace an equal entry if we find it. If none item has been found in the linked list we will just add it at the beginning of the linked list.

The next important thing in HashMap is the resizing, so if the actual size of the map is above over a threshold (determined by the current number of buckets and the loadfactor, in our case 16*0.75=12) it will resize the backing array. Resize is always 2 * the current number of buckets, which is guranteed to be a power of two to not break the function to find the buckets.

Since the number of buckets change, we have to rehash all the current entries in our table. This is quite costly, so if you know how many items there are, you should initialize the HashMap with that count so it does not have to resize the whole time.

这篇关于关于Java中的HashMap实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！