关于java中的HashMap实现
我试图对hashmap进行研究并得出以下分析：
https://stackoverflow.com/questions/11596549/how-does-javas-hashmap-work-internally/18492835#18492835
Q1你们可以给我看一个简单的地图，你可以在其中显示过程……如何通过使用这个公式详细计算给定键的哈希码..计算位置哈希％（arrayLength-1））其中应该放置元素（桶号），假设我有这个hashMap
HashMap map=new HashMap();//HashMap key random order. map.put("Amit","Java"); map.put("Saral","J2EE"); Q2有时可能会发生2个不同对象的hashCodes相同。 在这种情况下，2个对象将保存在一个存储桶中，并将显示为LinkedList。 入口点是最近添加的对象。 该对象指的是具有下一个字段的其他对象，因此一个。 最后一个条目是指null。 你们能用真实的例子告诉我这个…… !!
。
“Amit”将被分发到第10个桶，因为有点twiddeling。 如果没有任何位置，它会转到第7个桶，因为2044535＆15 = 7.这怎么可能请详细说明整个计算..？
快照已更新……
而另一个图像是……
通过使用此公式详细计算给定键的哈希码
在String情况下，这是由String#hashCode();计算的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 < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; }
基本上遵循java doc中的等式
hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
关于这个实现需要注意的一件有趣的事情是String实际上缓存了它的哈希码。 它可以做到这一点，因为String是不可变的。
如果我计算String “Amit”的哈希码，它将产生这个整数：
System.out.println("Amit".hashCode()); > 2044535
让我们通过一个简单的放置到地图，但首先我们必须确定如何构建地图。 关于Java HashMap最有趣的事实是它总是有2 ^ n个桶。 因此，如果你调用它，默认的桶数是16，这显然是2 ^ 4。
在此映射上执行put操作，它将首先获取密钥的哈希码。 在这个哈希码上发生了一些奇特的比特，以确保不良的哈希函数（特别是那些在低位没有差异的哈希函数）不会“重载”一个桶。
实际负责将密钥分发给存储桶的实际function如下：
h & (length-1); // length is the current number of buckets, h the hashcode of the key
这仅适用于两个桶大小的功率，因为它使用＆将键映射到存储桶而不是模数。
“Amit”将被分发到第10个桶，因为有点twiddeling。 如果没有比特的话，它会进入第7个桶，因为2044535 & 15 = 7 。
现在我们有了它的索引，我们可以找到存储桶。 如果存储桶包含元素，我们必须迭代它们并在找到它时替换相等的条目。 如果在链表中没有找到任何项目，我们只需将其添加到链表的开头即可。
HashMap的下一个重要事项是resize，因此如果地图的实际大小超过阈值（由当前桶数和loadfactor确定，在我们的情况下为16 * 0.75 = 12），它将调整后备arrays的大小。 resize总是2 *当前桶的数量，这被保证是两个不破坏function以找到桶的功率。
由于桶的数量发生变化，我们必须重新整理表中的所有当前条目。 这是非常昂贵的，所以如果您知道有多少项，您应该使用该计数初始化HashMap ，这样就不必调整整个时间。
Q1：查看String对象的hashCode()方法实现
Q2：创建简单类并将其hashCode()方法实现为return 1 。 这意味着每个具有该类的对象将具有相同的hashCode，因此将保存在HashMap中的同一个存储桶中。
了解哈希代码有两个基本要求：
- 当为给定对象重新计算哈希码时（没有以改变其身份的方式在内部更改），它必须产生与先前计算相同的值。 类似地，两个“相同”对象必须产生相同的哈希码。
- 当针对两个不同对象（从其内部内容的角度来看不被认为是“相同的”）计算哈希码时，两个哈希码应该是不同的概率很高。
如何实现这些目标是研究这些目标的数学书生非常感兴趣的主题，但理解细节对理解哈希表的工作方式并不重要。
import java.util.Arrays; public class Test2 { public static void main(String[] args) { Map map = new Map(); map.put(1, "A"); map.put(2, "B"); map.put(3, "C"); map.put(4, "D"); map.put(5, "E"); System.out.println("Iterate"); for (int i = 0; i < map.size(); i++) { System.out.println(map.values()[i].getKey() + " : " + map.values()[i].getValue()); } System.out.println("Get-> 3"); System.out.println(map.get(3)); System.out.println("Delete-> 3"); map.delete(3); System.out.println("Iterate again"); for (int i = 0; i < map.size(); i++) { System.out.println(map.values()[i].getKey() + " : " + map.values()[i].getValue()); } } } class Map { private int size; private Entry[] entries = new Entry[16]; public void put(K key, V value) { boolean flag = true; for (int i = 0; i < size; i++) { if (entries[i].getKey().equals(key)) { entries[i].setValue(value); flag = false; break; } } if (flag) { this.ensureCapacity(); entries[size++] = new Entry(key, value); } } public V get(K key) { V value = null; for (int i = 0; i < size; i++) { if (entries[i].getKey().equals(key)) { value = entries[i].getValue(); break; } } return value; } public boolean delete(K key) { boolean flag = false; Entry[] entry = new Entry[size]; int j = 0; int total = size; for (int i = 0; i < total; i++) { if (!entries[i].getKey().equals(key)) { entry[j++] = entries[i]; } else { flag = true; size--; } } entries = flag ? entry : entries; return flag; } public int size() { return size; } public Entry[] values() { return entries; } private void ensureCapacity() { if (size == entries.length) { entries = Arrays.copyOf(entries, size * 2); } } @SuppressWarnings("hiding") public class Entry { private K key; private V value; public K getKey() { return key; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } public Entry(K key, V value) { super(); this.key = key; this.value = value; } } }