Android中的HashMap原理实践探索，重写equals()，为什么重写hashCode() 和 ==
HashMap的文章有很多
可以先读读相关文章，及原理篇。本篇主要是从实践探索里面的变化，再对比看原理就会更加清晰.
此话题虽然老生常谈：然而理论完了实践一把
其中不少收获，Android中的和Java的设计还是有所不同。
Android给的英文注释也是16，实践一把发现注释欺骗了你。
实践是检验真理的唯一标准。于是还是实践一把，验证一下，扩容因子，以及扩容演化，运算的过程步骤。
Android初始化数组不是16 各版本不一样
之前的是4，后来变成0，第一次put才给4.Android对内存的使用考虑是慎之又慎。
而且里面用到很多巧妙的位运算
和数据结构，算法设计。故而HashMap的探讨真是前赴后继，乐此不疲。
周末提起，又探究一翻，主要利用反射打印其变化过程。明白了其中不少道理，受益匪浅，其中一些位运算算法还未理解其精髓。这个若详细探究起来几天几夜也未必，做了个简易探索。有兴趣的可以一观， 不足之处，还望指正
HashMap 有局限不能查询区间问题。
Java8又用到红黑树。
前天翻书数据结构，说二叉树深度过大时出现了B树B+树。用于数据库之中，使用少量内存查询更高效查询对象。
相关文章
HashMap实现原理及源码分析
http://www.cnblogs.com/chengxiao/p/6059914.html
Java8系列之重新认识HashMap
https://zhuanlan.zhihu.com/p/21673805
HashMap的工作原理 提问篇
http://www.importnew.com/7099.html
深入Java集合学习系列：HashMap的实现原理
http://zhangshixi.iteye.com/blog/672697
HashMap实现原理分析(详解)
http://www.cnblogs.com/xingzc/p/5765572.html
从零 == 号开始吧
来来看例子
public static void main(String[] args) { String ss = "a"; int hashCode = ss.hashCode(); String s2 = "a"; int hashCode2 = s2.hashCode(); System.out.println(hashCode); System.out.println(hashCode2); System.out.println(ss == s2); System.out.println(ss.equals(s2)); }运行结果9797truetrue看例子
public static void main(String[] args) { String ss = "a"; int hashCode = ss.hashCode(); System.out.println(hashCode); String s2 = new String("a"); System.out.println(s2.hashCode()); System.out.println(ss == s2); System.out.println(ss.equals(s2)); } 运行结果9797falsetrue对比
public static void main(String[] args) { String ss = new String("a"); int hashCode = ss.hashCode(); System.out.println(hashCode); String s2 = new String("a"); System.out.println(s2.hashCode()); System.out.println(ss == s2); System.out.println(ss.equals(s2)); }运行结果9797falsetrue放在Set集合里面
public static void main(String[] args) { String ss = "a"; String s2 = "a"; String s3 = new String("a"); String s4 = new String("a"); Set set = new HashSet();// Set set = new TreeSet(); set.add(ss); set.add(s2); set.add(s3); set.add(s4); for (Object object : set) { System.out.println("set.size()===" + set.size() + " ; object=="+ object); } }运行结果set.size()===1 ; object==a在Set里面认为对象相等。
HashSet实现是利用了HashMap去进行的比较 看Add方法 ； 利用了静态全局变量 Value为相同的值 如果Key相同那么map中只有一个对象 ； 我们再看HashMap的put方法。
private transient HashMap map; private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } public boolean add(E e) { return map.put(e, PRESENT)==null; } HashMap上场 ， HashMap有多个版本，Android中的不同版本JDK24和JDK25不同
初始化容量也不同 不是我们看到的Java的16.
Java7和Java8的也不同 Java8用到红黑树等 默认的扩容因子还都是0.75
版本对比先不比较，比较了一个晚上都凌乱了。
HashMap put方法源码
先看AndroidSDK 25版本中的HashMap源码
自己点进去看一下。我们利用反射先看看初始化的属性
HashMap 网上原理一大堆没看一次，大有受益又有疑问，
实践是检验真理的唯一标准，我们来实践一下。
我们采用实践通过实践看原理
先建一个空的HashMap 反射一下
HashMap hashMap = new HashMap();ReflectUtils.getFildValue(hashMap);import java.lang.reflect.Array;import java.lang.reflect.Field;import java.lang.reflect.Modifier;public class ReflectUtils { public static void getFildValue(Object object) { Field[] fields = object.getClass().getDeclaredFields(); System.out.println("----------------------start----------------------------------------------------------------------------"); System.out.println("class :" + object.getClass()); for(Field f : fields){ f.setAccessible(true); int mod = f.getModifiers(); Object o = null; try { o = f.get(object); System.out.println( Modifier.toString(mod) + " " + f.getType().getName() + " " + f.getName() + " == " + o); if (o != null) { Class<?> type = o.getClass(); if (type.isArray()) { System.out.println("是数组："+type.isArray()); Class<?> elementType = type.getComponentType(); System.out.println("Array of: " + elementType); System.out.println("Array length: " + Array.getLength(o)); } } } catch (IllegalAccessException e) { e.printStackTrace(); } System.out.println("------------------------"); } System.out.println("----------------------end-------------------------------------------------------------------------"); }}然后我们看到各种的初始化的值 对于static final的不会改变 以后就不再打印
I/System.out: transient [Ljava.util.HashMapHashMapEntry;table==[Ljava.util.HashMapHashMapEntry;@6ca7431
这个是数组。
不会变化的 记住就行static final int DEFAULT_INITIAL_CAPACITY = 4; //默认初始化容量static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认扩容因子static final HashMapEntry<?,?>[] EMPTY_TABLE = {}; //空的数组final float loadFactor = DEFAULT_LOAD_FACTOR; //默认扩容因子会变化的变量transient HashMapEntry[] table = (HashMapEntry[]) EMPTY_TABLE;transient int size; //是hashmap的元素个数int threshold; //临界值; transient int modCount; //修改次数I/System.out: ----------------------start----------------------------------------------------------------------------I/System.out: class :class java.util.HashMapI/System.out: private transient java.util.Set entrySet == nullI/System.out: ------------------------I/System.out: final float loadFactor == 0.75I/System.out: ------------------------I/System.out: transient int modCount == 0I/System.out: ------------------------I/System.out: transient int size == 0I/System.out: ------------------------I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@6ca7431I/System.out: 是数组：trueI/System.out: Array of: class java.util.HashMap$HashMapEntryI/System.out: Array length: 0I/System.out: ------------------------I/System.out: int threshold == 4I/System.out: ------------------------I/System.out: static final int DEFAULT_INITIAL_CAPACITY == 4I/System.out: ------------------------I/System.out: static final float DEFAULT_LOAD_FACTOR == 0.75I/System.out: ------------------------I/System.out: static final [Ljava.util.HashMap$HashMapEntry; EMPTY_TABLE == [Ljava.util.HashMap$HashMapEntry;@6ca7431I/System.out: 是数组：trueI/System.out: Array of: class java.util.HashMap$HashMapEntryI/System.out: Array length: 0I/System.out: ------------------------I/System.out: static final int MAXIMUM_CAPACITY == 1073741824I/System.out: ------------------------I/System.out: private static final long serialVersionUID == 362498820763181265I/System.out: ------------------------I/System.out: ----------------------end------------------------------------------------------------------------- 再来一个方法只打印变化的量 final的都不再打印。
public static void getFildValueNoFinal(Object object) { Field[] fields = object.getClass().getDeclaredFields(); System.out.println("----------------------start----------------------------------------------------------------------------"); System.out.println("class :" + object.getClass()); for(Field f : fields){ f.setAccessible(true); int mod = f.getModifiers(); String modifierString = Modifier.toString(mod); if (!modifierString.contains("final")){ Object o = null; try { o = f.get(object); System.out.println(modifierString + " " + f.getType().getName() + " " + f.getName() + " == " + o); if (o != null) { Class<?> type = o.getClass(); if (type.isArray()) { Class<?> elementType = type.getComponentType(); System.out.println("Array of: " + elementType); System.out.println("Array length: " + Array.getLength(o)); } } } catch (IllegalAccessException e) { e.printStackTrace(); } System.out.println("------------------------"); } } System.out.println("----------------------end-------------------------------------------------------------------------"); }f
hashMap.put("1", "abc");ReflectUtils.getFildValueNoFinal(hashMap);hashMap.put("2", "abc");ReflectUtils.getFildValueNoFinal(hashMap);初始化数据 entrySet == null table.length == 0 modCount == 0 sise == 0 threshold == 4; //临界值分别添加1个数据和添加两个数据发生了哪些变化添加1数据 entrySet == null table.length == 4 modCount == 1 size == 1 threshold == 3；添加2数据 entrySet == null table.length == 4 modCount == 2 size == 2 threshold == 3；我们直接制作输成表格 改造下的代码I/System.out: ----------------------start----------------------------------------------------------------------------I/System.out: class :class java.util.HashMapI/System.out: private transient java.util.Set entrySet == nullI/System.out: ------------------------I/System.out: transient int modCount == 1I/System.out: ------------------------I/System.out: transient int size == 1I/System.out: ------------------------I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@2809716I/System.out: Array of: class java.util.HashMap$HashMapEntryI/System.out: Array length: 4I/System.out: ------------------------I/System.out: int threshold == 3I/System.out: ------------------------I/System.out: ----------------------end-------------------------------------------------------------------------I/System.out: ----------------------start----------------------------------------------------------------------------I/System.out: class :class java.util.HashMapI/System.out: private transient java.util.Set entrySet == nullI/System.out: ------------------------I/System.out: transient int modCount == 2I/System.out: ------------------------I/System.out: transient int size == 2I/System.out: ------------------------I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@2809716I/System.out: Array of: class java.util.HashMap$HashMapEntryI/System.out: Array length: 4I/System.out: ------------------------I/System.out: int threshold == 3I/System.out: ------------------------I/System.out: ----------------------end-------------------------------------------------------------------------我们直接制作输成表格 改造下的代码 这是 扩容的规律，思考一下 负载因子是0.75
I: | entrySet == null | modCount == 1 | size == 1 | table.length==4 | threshold == 3 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 2 | size == 2 | table.length==4 | threshold == 3 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 3 | size == 3 | table.length==4 | threshold == 3 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 4 | size == 4 | table.length==8 | threshold == 6 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 5 | size == 5 | table.length==8 | threshold == 6 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 6 | size == 6 | table.length==8 | threshold == 6 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 7 | size == 7 | table.length==16 | threshold == 12 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 8 | size == 8 | table.length==16 | threshold == 12 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 9 | size == 9 | table.length==16 | threshold == 12 | I: ----------------------------------------------------------------------------------------------..I: | entrySet == null | modCount == 12 | size == 12 | table.length==16 | threshold == 12 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 13 | size == 13 | table.length==32 | threshold == 24 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 14 | size == 14 | table.length==32 | threshold == 24 | I: ----------------------------------------------------------------------------------------------..| entrySet == null | modCount == 26 | size == 26 | table.length==32 | threshold == 24 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 27 | size == 27 | table.length==64 | threshold == 48 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 28 | size == 28 | table.length==64 | threshold == 48 | I: ----------------------------------------------------------------------------------------------..I: | entrySet == null | modCount == 49 | size == 49 | table.length==64 | threshold == 48 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 50 | size == 50 | table.length==128 | threshold == 96 | I: ----------------------------------------------------------------------------------------------..I: | entrySet == null | modCount == 96 | size == 96 | table.length==128 | threshold == 96 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 97 | size == 97 | table.length==256 | threshold == 192 | I: ----------------------------------------------------------------------------------------------..I: | entrySet == null | modCount == 192 | size == 192 | table.length==256 | threshold == 192 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 193 | size == 193 | table.length==512 | threshold == 384 | ..I: | entrySet == null | modCount == 385 | size == 385 | table.length==512 | threshold == 384 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 386 | size == 386 | table.length==1024 | threshold == 768 | I: ----------------------------------------------------------------------------------------------..| entrySet == null | modCount == 769 | size == 769 | table.length==1024 | threshold == 768 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 770 | size == 770 | table.length==2048 | threshold == 1536 | ..I: | entrySet == null | modCount == 1537 | size == 1537 | table.length==2048 | threshold == 1536 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 1538 | size == 1538 | table.length==4096 | threshold == 3072 | ..I: | entrySet == null | modCount == 3072 | size == 3072 | table.length==4096 | threshold == 3072 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 3073 | size == 3073 | table.length==8192 | threshold == 6144 | ..I: | entrySet == null | modCount == 6144 | size == 6144 | table.length==8192 | threshold == 6144 | I: ----------------------------------------------------------------------------------------------I: | entrySet == null | modCount == 6145 | size == 6145 | table.length==16384 | threshold == 12288 | I: ----------------------------------------------------------------------------------------------// Android-Note：我们总是使用0.75的负载因子，并且明确忽略所选值。
并且Android中严格使用0.75 其他的输入的 值直接忽略掉，所以只能更改初始值tabled的长度。负载因子不能改变
无论输入0.5和0.2还是0.9都不起作用。
其中方法的演化在后面inflateTable(threshold); 和 里面的
int capacity = roundUpToPowerOf2(toSize);
Integer.highestOneBit(number) 和 (Integer.bitCount(number)
这几个方法在后面推导
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); int i = indexFor(hash, table.length); for (HashMapEntry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } hashmap = new HashMap时。
transient HashMapEntry
static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }这个算法int h为hashcode int类型 int length 为 2的次方得到结果
length == 4 length - 1 = 3 得到的值也为0123，0123，循环
length == 8 length - 1 = 7 得到的值也为01234567，01234567，循环
StringBuilder stringBuffer = new StringBuilder(); for (int i = 0; i < 10000; i++) { stringBuffer.append(i & 3).append(","); } System.out.println(stringBuffer.toString());结果0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,i & 7 时 结果0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1,2,3,4就会得到小于数组长度的一个i值。然后遍历数组，
for (HashMapEntry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } 譬如 我们map.put(“0”,”a”); map.put(“1”,”a”);map.put(“2”,”a”); map.put(“4”,”a”);
I: "0".hash==-554176856I: "1".hash==-80388575I: "2".hash== 178623694I: "4".hash==1342561432I: "0".hash & 3==0I: "1".hash & 3==1I: "2".hash & 3==2I: "4".hashCode() & 3==0放入四个数，此时table.length = 4
hashcode各不相同，但是int i = indexFor(int h, int length) 里面却有重复
map.put(“0”,”a”); e = table[0] 此时 e == null 走下面的
addEntry(hash, key, value, i); 方法 发现条件不满足扩容就执行下面的createEntry方法。
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }执行createEntry方法。 此时创建了一个对象。
void createEntry(int hash, K key, V value, int bucketIndex) { HashMapEntry e = table[bucketIndex]; table[bucketIndex] = new HashMapEntry<>(hash, key, value, e); size++; } 先拿到当前位置的对象是第一次此时为null 先临时变量记录下来
HashMapEntry e = table[bucketIndex]; 然后当前位置的数组指向新创建的对象，并将 hash值 key值 value值，和刚才被替换掉的对象记录下来。
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
static class HashMapEntry<K,V> implements Map.Entry<K,V> { final K key; V value; HashMapEntry next; int hash; HashMapEntry(int h, K k, V v, HashMapEntry n){ value = v; next = n; key = k; hash = h; }} map.put(“0”,”a”);
table[0] = new HashMapEntry(-554176856, “0”,”a”,null);
map.put(“1”,”a”);
table[1] = new HashMapEntry(-80388575, “1”,”a”,null);
map.put(“2”,”a”);
table[2] = new HashMapEntry(178623694, “2”,”a”,null);
然后我们 map.put(“4”,”a”);
此时 “4”.hash==1342561432 ; table.legth == 4 ;
i= “4”.hash & 3 == 0
在 e = table[0] 已经存在了一个值。 此时 e != null 那么进入for循环进行判断
e = table[0] = new HashMapEntry(-554176856, “0”,”a”,null);
此时两个在一个数组位置上，开始判断是替换此链表的位置还是再后面添加一个？
发现 此时 e.hash == -554176856
hash = “4”.hash == 1342561432
e.hash != hash
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {key.equals(k) = false
此时跳出循环 继续创建 那么 按上面的流程
HashMapEntry e = table[bucketIndex];table[bucketIndex] = new HashMapEntry<>(hash, key, value, e); HashMapEntry next = new HashMapEntry( -554176856, “0”,”a”,null);
table[0] = new HashMapEntry(1342561432, “4”,”a”, next );
这就意味着table[0] 链表上两个值。
table[0] = new HashMapEntry(1342561432, “4”,”a”, new HashMapEntry( -554176856, “0”,”a”,null) )
如果map.put(“4”,”a”); 换成 如果map.put(“0”,”b”);
此时已然是table[0]上进行操作 并且hashe相同进入循环
e.hash == -554176856 ; e.hash == hash = true
并且 由于key为字符串 那么((k = e.key) == key 为True
此时进行替换Value操作
table[0] next = new HashMapEntry(-554176856, “0”,”b”,null);
加入Key不为字符串 Hashcode相同 ((k = e.key) == key不相同此时就要进行 || equals比较啦。
hashcode 为 int 类型 其中 字符串的数量一定大于int类型的数量
因此两个对象就存在hashcode相等的时候，此时我们用==号比较地址，地址相同一定是同一个对象。
这时假如我们表示去重操作，两个学生名字，学号一样，我们认为一个学生。我们在内存中创建了两个，那么怎么表示使用equals方法比较对相关的相等，就去重写equals方法
学号相等 和 姓名相等就返回true 此时，他们的equals相等了。进行判断没有错。
即使他们的hasecode不相等，
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 看这行代码也是成立的，会替换原有的值。
那么问题发生的真正原因是什么呢？
我们来看个例子吧。
此时我们重写equals 不重写hashcode
public class Student { private String name; int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; if (age != student.age) return false; return name != null ? name.equals(student.name) : student.name == null; }// @Override// public int hashCode() {// int result = name != null ? name.hashCode() : 0;// result = 31 * result + age;// return result;// }}传入相同姓名和年龄
Student student = new Student("danjiang", 18);Student student1 = new Student("danjiang", 18);Log.d("TAG", "" + student.equals(student1));运行结果： D/TAG: true运行结果 是相等的。 其他任何地方也是相等的 equals 具有对称性 自反性 等等
那么我们看HashMap里面却不认可，不给k赋值了，一个为null 另一个是真实的对象，放入其中认为是两个对象。
HashMap hashMap = new HashMap(); Student student = new Student("danjiang", 18); Student student1 = new Student("danjiang", 18); hashMap.put(student, "a"); hashMap.put(student1, "a"); Log.d("TAG", "hashMap.size()==" + hashMap.size()); 运行结果： D/TAG: hashMap.size()==2if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
再来看这句话 || key.equals(k) 认为相等可以替换啊，那么为啥不让会出现两个。
student@4841 code 1617119160 table[0]
student@4842 code -35303204 table[0]
student@4843 code -2050440646 table[2]
student@4840 code 1439680537 table[1]
此时两个对象即使发生在同一维数组上
因为 hasecode不相等那么 ((k = student) == student1没有执行 也就是 Object k =null;
student1.equals(k) 为 false.
Student student = new Student("danjiang", 18); Student student1 = new Student("danjiang", 18); Object k =null; if (student.hashCode() == student1.hashCode() && ((k = student) == student1 || student1.equals(k))) { Log.d("TAG", "" + k); } Log.d("TAG", "结束" + k);D/TAG: 结束nullhashCode方法可以这样理解：它返回的就是根据对象的内存地址换算出的一个值
hashmap中认为，hashCode不相等，两个对象就不一样。 这才是要害。
所以我们使用hashmap不得不重写hashcode
那么假如我们有无限大的内存，无穷多个对象，那么他们中间HashCode总有相等的吧。
if (true && ((k = student) == student1 || student1.equals(k))) { Log.d("TAG", "" + k); }此时即使(k = student) == student1为false 那么 还有equals 就认为是一个对象了。
是Hashcode重复了， equals里面还比较了类名，属性值。
所以当我们认为两个对象相等时既要重写equals 又要 重写HashCode
看看Object里面的解释。
*返回对象的哈希码值。这个方法是 *支持哈希表的利益，如提供的哈希表 {@link java.util.HashMap}{@code hashCode}的一般合同是： 无论何时在同一个对象上调用多次执行Java应用程序，{@code hashCode}方法必须始终返回相同的整数，没有提供任何信息用于{@code equals}对象的比较被修改。这个整数不需要从一个执行中保持一致应用于另一个执行相同的应用程序。 如果两个对象根据{@code equals（Object）}相等，方法，然后在每个方法上调用{@code hashCode}方法两个对象必须产生相同的整数结果。 这是不要求，如果两个对象不相等根据{@link java.lang.Object＃equals（java.lang.Object）}方法，然后在每个方法上调用{@code hashCode}方法两个对象必须产生不同的整数结果。但是，那程序员应该知道产生不同的整数结果对于不相等的对象可能会提高散列表的性能。尽可能多的合理实用，hashCode方法定义class {@code Object}确实返回不同的整数对象。 （这通常通过转换内部来实现将对象的地址变成一个整数，但这个实现技术是不需要的Java＆trade;编程语言。）@see java.lang.Object＃equals（java.lang.Object） @see java.lang.System＃identityHashCodeequals 非空调用对称性传递性自己是自己的反身 盗一张结构图吧。 
JDK8用的红黑树 再来一张
搞了一天一夜。看也看累了吧。
来张美女提提神
下面是扩容相关方法。
在put里面数据， table的长度根据threshold阀值，如上图表格所示以二倍容量扩容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
这个方法初始化时，因为 这个定义， 返回一个会给table设定一个长度，默认不输入的化就是4 注意Android的
transient HashMapEntry
private void inflateTable(int toSize) { int capacity = roundUpToPowerOf2(toSize); float thresholdFloat = capacity * loadFactor; if (thresholdFloat > MAXIMUM_CAPACITY + 1) { thresholdFloat = MAXIMUM_CAPACITY + 1; } threshold = (int) thresholdFloat; table = new HashMapEntry[capacity]; }这个方法比较绕也是醉了。 改写一下吧
private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; int rounded = number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (rounded = Integer.highestOneBit(number)) != 0 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded : 1; return rounded; }改写之后
public static int test(int number) { int rounded = 0; if (number >= MAXIMUM_CAPACITY) { rounded = MAXIMUM_CAPACITY; } else { rounded = Integer.highestOneBit(number); if (rounded != 0) { if (Integer.bitCount(number) > 1) { rounded = rounded << 1; } } else { rounded = 1; } } return rounded; }int roundUpToPowerOf2(int number)这个方法的执行执行规律是
-3==0-2==0-1==00==11==12==23==44==45==86==87==88==89==1610==1611==16.16==1617==32.64==6465==128小于0的就为零
0==1 为零时 为1
int x= Integer.highestOneBit(number) public static int highestOneBit(int var0) { var0 |= var0 >> 1; var0 |= var0 >> 2; var0 |= var0 >> 4; var0 |= var0 >> 8; var0 |= var0 >> 16; return var0 - (var0 >>> 1);}简单的说法
如果一个数是0, 则返回0；
如果是负数, 则返回 -2147483648：【1000,0000,0000,0000,0000,0000,0000,0000】(二进制表示的数)；
如果是正数, 返回的则是跟它最靠近的比它小的2的N次方
比如 17：
二进制是【0000,0000,0000,0000,0000,0000,0001,0001】
highestOneBit(17)返回的是最高位的1个1, 其它全是0 的二进制数：【0000,0000,0000,0000,0000,0000,0001,0000】，其实就是16。
int rounded= Integer.highestOneBit(number)
rounded = {–2147483648,0,1,2,,4,8,16,32,64……}
if (Integer.bitCount(number) > 1) {
rounded = rounded << 1;
}
int x = -2147483648 << 1; == 0System.out.println(x); x == 0这时所有的负值全部转化成0int ii[] = {-2147483648,1,2,4,8,16,32,64}; for (int i = 0; i < ii.length; i++) { int hh = ii[i] << 1; System.out.println(hh);}0248163264128.-2==-2147483648-1==-21474836480==01==12==23==24==4.7==48==8.15==816==16.31==1632==32.这个方法有其精妙之处，可以多百度一下。
Integer.bitCount(number) public static int bitCount(int var0) { var0 -= var0 >>> 1 & 1431655765; var0 = (var0 & 858993459) + (var0 >>> 2 & 858993459); var0 = var0 + (var0 >>> 4) & 252645135; var0 += var0 >>> 8; var0 += var0 >>> 16; return var0 & 63; }Integer.bitCount(number)得到的值除了0为0之外其他全部为正值。
AdnroidSDK 23版本中初始化长度为 4 >>> 1 = 2private static final int MINIMUM_CAPACITY = 4;private static final Entry[] EMPTY_TABLE = new HashMapEntry[MINIMUM_CAPACITY >>> 1];AndroidSDK25 初始化列表长度是4AndroidSDK24 hash值得来源也不一样int hash = Collections.secondaryHash(key);AndroidSDK25 hash值得来源也不一样int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);JDK 8版本中的 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }/**
* Maps the specified key to the specified value.
*
* @param key
* the key.
* @param value
* the value.
* @return the value of any previous mapping with the specified key or
* {@code null} if there was no such mapping.
*/
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key); HashMapEntry[] tab = table; int index = hash & (tab.length - 1); for (HashMapEntry e = tab[index]; e != null; e = e.next) { if (e.hash == hash && key.equals(e.key)) { preModify(e); V oldValue = e.value; e.value = value; return oldValue; } } // No entry for (non-null) key is present; create one modCount++; if (size++ > threshold) { tab = doubleCapacity(); index = hash & (tab.length - 1); } addNewEntry(key, value, hash, index); return null;} JDK8中的比较再之后再比较先看Object 类/**
* Returns a hash code value for the object. This method is
* supported for the benefit of hash tables such as those provided by
* {@link java.util.HashMap}.
*
* The general contract of {@code hashCode} is:
*
*- Whenever it is invoked on the same object more than once during
* an execution of a Java application, the {@code hashCode} method
* must consistently return the same integer, provided no information
* used in {@code equals} comparisons on the object is modified.
* This integer need not remain consistent from one execution of an
* application to another execution of the same application.
* - If two objects are equal according to the {@code equals(Object)}
* method, then calling the {@code hashCode} method on each of
* the two objects must produce the same integer result.
* - It is not required that if two objects are unequal
* according to the {@link java.lang.Object#equals(java.lang.Object)}
* method, then calling the {@code hashCode} method on each of the
* two objects must produce distinct integer results. However, the
* programmer should be aware that producing distinct integer results
* for unequal objects may improve the performance of hash tables.
*
*
* As much as is reasonably practical, the hashCode method defined by
* class {@code Object} does return distinct integers for distinct
* objects. (This is typically implemented by converting the internal
* address of the object into an integer, but this implementation
* technique is not required by the
* Java™ programming language.)
*
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
*/
public native int hashCode();
/ ** *返回对象的哈希码值。这个方法是 *支持哈希表的利益，如提供的哈希表 * {@link java.util.HashMap}。 * * {@code hashCode}的一般合同是： *
* - 无论何时在同一个对象上调用多次 *执行Java应用程序，{@code hashCode}方法 *必须始终返回相同的整数，没有提供任何信息 *用于{@code equals}对象的比较被修改。 *这个整数不需要从一个执行中保持一致 *应用于另一个执行相同的应用程序。 *
- 如果两个对象根据{@code equals（Object）}相等， *方法，然后在每个方法上调用{@code hashCode}方法 *两个对象必须产生相同的整数结果。 *
- 这是不要求，如果两个对象不相等 *根据{@link java.lang.Object＃equals（java.lang.Object）} *方法，然后在每个方法上调用{@code hashCode}方法 *两个对象必须产生不同的整数结果。但是，那 *程序员应该知道产生不同的整数结果 *对于不相等的对象可能会提高散列表的性能。 * *
*尽可能多的合理实用，hashCode方法定义 * class {@code Object}确实返回不同的整数 *对象。 （这通常通过转换内部来实现 *将对象的地址变成一个整数，但这个实现 *技术是不需要的 Java＆trade;编程语言。） * * @返回此对象的哈希码值。 * @see java.lang.Object＃equals（java.lang.Object） * @see java.lang.System＃identityHashCode * / public native int hashCode（）;
/**
* Indicates whether some other object is “equal to” this one.
*
* The {@code equals} method implements an equivalence relation
* on non-null object references:
*
*- It is reflexive: for any non-null reference value
* {@code x}, {@code x.equals(x)} should return
* {@code true}.
* - It is symmetric: for any non-null reference values
* {@code x} and {@code y}, {@code x.equals(y)}
* should return {@code true} if and only if
* {@code y.equals(x)} returns {@code true}.
* - It is transitive: for any non-null reference values
* {@code x}, {@code y}, and {@code z}, if
* {@code x.equals(y)} returns {@code true} and
* {@code y.equals(z)} returns {@code true}, then
* {@code x.equals(z)} should return {@code true}.
* - It is consistent: for any non-null reference values
* {@code x} and {@code y}, multiple invocations of
* {@code x.equals(y)} consistently return {@code true}
* or consistently return {@code false}, provided no
* information used in {@code equals} comparisons on the
* objects is modified.
* - For any non-null reference value {@code x},
* {@code x.equals(null)} should return {@code false}.
*
*
* The {@code equals} method for class {@code Object} implements
* the most discriminating possible equivalence relation on objects;
* that is, for any non-null reference values {@code x} and
* {@code y}, this method returns {@code true} if and only
* if {@code x} and {@code y} refer to the same object
* ({@code x == y} has the value {@code true}).
*
* Note that it is generally necessary to override the {@code hashCode}
* method whenever this method is overridden, so as to maintain the
* general contract for the {@code hashCode} method, which states
* that equal objects must have equal hash codes.
*
* @param obj the reference object with which to compare.
* @return {@code true} if this object is the same as the obj
* argument; {@code false} otherwise.
* @see #hashCode()
* @see java.util.HashMap
*/
public boolean equals(Object obj) {
return (this == obj);
}
/ **
*表示某个其他对象是否等于此。
*
* {@code equals}方法实现等价关系
*非空对象引用：
*
*- 它是反身：对于任何非空参考值
* {@code x}，{@code x.equals（x）}应该返回
* {@code true}。
* - 对于对称：对于任何非空引用值
* {@code x}和{@code y}，{@code x.equals（y）}
*只要返回{@code true}
* {@code y.equals（x）}返回{@code true}。
* - 它是传递：对于任何非空参考值
* {@code x}，{@code y}和{@code z}，if
* {@code x.equals（y）}返回{@code true}和
* {@code y.equals（z）}返回{@code true}，然后
* {@code x.equals（z）}应该返回{@code true}。
* - ：对于任何非空参考值
* {@code x}和{@code y}，多次调用
* {@code x.equals（y）}始终返回{@code true}
*或一直返回{@code false}，提供否
*在{@code等}比较中使用的信息
*对象被修改。
* - 对于任何非空引用值{@code x}，
* {@code x.equals（null）}应该返回{@code false}。
*
*
*类{@code Object}的{@code equals}方法实现
*对象上最可区别的可能的等价关系;
*就是对于任何非空参考值{@code x}和
* {@code y}，此方法返回{@code true}
*如果{@code x}和{@code y}引用相同的对象
*（{@code x == y}的值为{@code true}）。
*
*请注意，通常需要覆盖{@code hashCode}
*方法，只要这个方法被覆盖，以便维护
* {@code hashCode}方法的一般合同，其中规定
*相等的对象必须具有相等的哈希码。
*
* @param obj要与之比较的引用对象。
* @return {@code true}如果此对象与obj相同
*论证{@code false}否则。
* @see #hashCode（）
* @see java.util.HashMap
* /
public boolean equals（Object obj）{
return（this == obj）;
}
类 java.lang.System类 java.lang.System
/**
* Returns the same hash code for the given object as
* would be returned by the default method hashCode(),
* whether or not the given object’s class overrides
* hashCode().
* The hash code for the null reference is zero.
*
* @param x object for which the hashCode is to be calculated
* @return the hashCode
* @since JDK1.1
*/
public static native int identityHashCode(Object x);
“`
/**
*返回与给定对象相同的哈希码
*将由默认方法hashCode（）返回，
*给定对象的类是否覆盖
* hashCode（）。
*空引用的哈希码为零。
*
*要为其计算hashCode的@param x对象
* @返回hashCode
* @since JDK1.1
*/
public static native int identityHashCode（Object x）;
其中一些原理没有细讲，大家可以看文章开头的相关博客。
各种分析比较详尽。
周末探索两天一个通宵发现内容设计好多不能一一尽述。以后周末闲了，再进行探索。
在整理Kotlin, 看到周末未完成的草稿稍微整理一下。
欢迎拍砖。
更多相关文章
- Android搜索控件的基本使用方法
- Android官方离线文档（API文档）打开速度慢的解决方法
- Android IPC机制（三）在Android Studio中使用AIDL实现跨进程方法调
- android实现观察者模式的几种方法
- Android Studio怎样提示函数使用方法
- 【Android 性能优化】应用启动优化 ( 安卓应用启动分析 | Launch
- Android方法数
- 改变Android按钮背景颜色的高效方法
- Android双击返回键退出程序的实现方法