HashMap实现原理深度探索，重写equals()，为什么重写hashCode() 和 ==

来看例子

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));
 }
运行结果
97
97
true
true

看例子

 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));
 }
 运行结果
97
97
false
true

对比

 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));
 }
运行结果
97
97
false
true

放在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<E,Object> 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.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@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<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
transient int size; //是hashmap的元素个数
int threshold;  //临界值; 
transient int modCount; //修改次数

I/System.out: ----------------------start----------------------------------------------------------------------------
I/System.out: class :class java.util.HashMap
I/System.out: private transient java.util.Set entrySet == null
I/System.out: ------------------------
I/System.out: final float loadFactor == 0.75
I/System.out: ------------------------
I/System.out: transient int modCount == 0
I/System.out: ------------------------
I/System.out: transient int size == 0
I/System.out: ------------------------
I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@6ca7431
I/System.out: 是数组：true
I/System.out: Array of: class java.util.HashMap$HashMapEntry
I/System.out: Array length: 0
I/System.out: ------------------------
I/System.out:  int threshold == 4
I/System.out: ------------------------
I/System.out: static final int DEFAULT_INITIAL_CAPACITY == 4
I/System.out: ------------------------
I/System.out: static final float DEFAULT_LOAD_FACTOR == 0.75
I/System.out: ------------------------
I/System.out: static final [Ljava.util.HashMap$HashMapEntry; EMPTY_TABLE == [Ljava.util.HashMap$HashMapEntry;@6ca7431
I/System.out: 是数组：true
I/System.out: Array of: class java.util.HashMap$HashMapEntry
I/System.out: Array length: 0
I/System.out: ------------------------
I/System.out: static final int MAXIMUM_CAPACITY == 1073741824
I/System.out: ------------------------
I/System.out: private static final long serialVersionUID == 362498820763181265
I/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.HashMap
I/System.out: private transient java.util.Set entrySet == null
I/System.out: ------------------------
I/System.out: transient int modCount == 1
I/System.out: ------------------------
I/System.out: transient int size == 1
I/System.out: ------------------------
I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@2809716
I/System.out: Array of: class java.util.HashMap$HashMapEntry
I/System.out: Array length: 4
I/System.out: ------------------------
I/System.out:  int threshold == 3
I/System.out: ------------------------
I/System.out: ----------------------end-------------------------------------------------------------------------
I/System.out: ----------------------start----------------------------------------------------------------------------
I/System.out: class :class java.util.HashMap
I/System.out: private transient java.util.Set entrySet == null
I/System.out: ------------------------
I/System.out: transient int modCount == 2
I/System.out: ------------------------
I/System.out: transient int size == 2
I/System.out: ------------------------
I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@2809716
I/System.out: Array of: class java.util.HashMap$HashMapEntry
I/System.out: Array length: 4
I/System.out: ------------------------
I/System.out:  int threshold == 3
I/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<K,V> 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<K,V>[] table
初始化数据 entrySet == null table.length == 0 modCount == 0 sise == 0 threshold == 4;
// threshold 临界值
第一次put时一个值时
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
会初始化确定一个值HashMapEntry<K,V>[] table 长度，这里table.length==4
I: | entrySet == null | modCount == 1 | size == 1 | table.length==4 | threshold == 3 |

if (key == null)
return putForNullKey(value);
如果为空就调用这个 并返回HashMap允许空key值为空。

int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
然后根据key 拿到 hash值。
int i = indexFor(hash, table.length); 然后根据Hash值和当前table的长度
看上面table.length 为二倍扩容 所以为4 8 16 32 64 128 以此类推 2的n次方

 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<K,V> 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==-554176856
I: "1".hash==-80388575
I: "2".hash== 178623694
I: "4".hash==1342561432
I: "0".hash & 3==0
I: "1".hash & 3==1
I: "2".hash & 3==2
I: "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<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
    }

先拿到当前位置的对象是第一次此时为null 先临时变量记录下来

HashMapEntry<K,V> 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<K,V> next;
        int hash;
        
        HashMapEntry(int h, K k, V v, HashMapEntry<K,V> 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<K,V> 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()==2

if (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: 结束null

hashCode方法可以这样理解：它返回的就是根据对象的内存地址换算出的一个值
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}的一般合同是： <li>无论何时在同一个对象上调用多次执行Java应用程序，{@code hashCode}方法必须始终返回相同的整数，没有提供任何信息用于{@code equals}对象的比较被修改。这个整数不需要从一个执行中保持一致应用于另一个执行相同的应用程序。<li>如果两个对象根据{@code equals（Object）}相等，方法，然后在每个方法上调用{@code hashCode}方法两个对象必须产生相同的整数结果。<li>这是<em>不</ em>要求，如果两个对象不相等根据{@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

equals 非空调用
对称性
传递性
自己是自己的反身

盗一张结构图吧。


这里写图片描述

JDK8用的红黑树 再来一张

这里写图片描述
这里写图片描述

搞了一天一夜。看也看累了吧。
来张美女提提神


这里写图片描述

下面是扩容相关方法。
在put里面数据， table的长度根据threshold阀值，如上图表格所示以二倍容量扩容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
这个方法初始化时，因为 这个定义， 返回一个会给table设定一个长度，默认不输入的化就是4 注意Android的
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;

    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==0
0==1
1==1
2==2
3==4
4==4
5==8
6==8
7==8
8==8
9==16
10==16
11==16
.
16==16
17==32
.
64==64
65==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; == 0
System.out.println(x); x == 0
这时所有的负值全部转化成0


int 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);
}

0
2
4
8
16
32
64
128

.
-2==-2147483648
-1==-2147483648
0==0
1==1
2==2
3==2
4==4
.
7==4
8==8
.
15==8
16==16
.
31==16
32==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 = 2
private static final int MINIMUM_CAPACITY = 4;
private static final Entry[] EMPTY_TABLE
            = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

AndroidSDK25  初始化列表长度是4
 
AndroidSDK24  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<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (HashMapEntry<K, V> 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}.
* <p>
* The general contract of {@code hashCode} is:
* <ul>
* <li>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.
* <li>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.
* <li>It is <em>not</em> 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.
* </ul>
* <p>
* 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}。
     * <p>
     * {@code hashCode}的一般合同是：
     * <ul>
     * <li>无论何时在同一个对象上调用多次
     *执行Java应用程序，{@code hashCode}方法
     *必须始终返回相同的整数，没有提供任何信息
     *用于{@code equals}对象的比较被修改。
     *这个整数不需要从一个执行中保持一致
     *应用于另一个执行相同的应用程序。
     * <li>如果两个对象根据{@code equals（Object）}相等，
     *方法，然后在每个方法上调用{@code hashCode}方法
     *两个对象必须产生相同的整数结果。
     * <li>这是<em>不</ em>要求，如果两个对象不相等
     *根据{@link java.lang.Object＃equals（java.lang.Object）}
     *方法，然后在每个方法上调用{@code hashCode}方法
     *两个对象必须产生不同的整数结果。但是，那
     *程序员应该知道产生不同的整数结果
     *对于不相等的对象可能会提高散列表的性能。
     * </ ul>
     * <p>
     *尽可能多的合理实用，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.
* <p>
* The {@code equals} method implements an equivalence relation
* on non-null object references:
* <ul>
* <li>It is <i>reflexive</i>: for any non-null reference value
* {@code x}, {@code x.equals(x)} should return
* {@code true}.
* <li>It is <i>symmetric</i>: 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}.
* <li>It is <i>transitive</i>: 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}.
* <li>It is <i>consistent</i>: 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.
* <li>For any non-null reference value {@code x},
* {@code x.equals(null)} should return {@code false}.
* </ul>
* <p>
* 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}).
* <p>
* 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);
}

/ **
*表示某个其他对象是否等于此。
* <p>
* {@code equals}方法实现等价关系
*非空对象引用：
* <ul>
* <li>它是<i>反身</ i>：对于任何非空参考值
* {@code x}，{@code x.equals（x）}应该返回
* {@code true}。
* <li>对于<i>对称</ i>：对于任何非空引用值
* {@code x}和{@code y}，{@code x.equals（y）}
*只要返回{@code true}
* {@code y.equals（x）}返回{@code true}。
* <li>它是<i>传递</ i>：对于任何非空参考值
* {@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}。
* <li> <i> <i> </ i>：对于任何非空参考值
* {@code x}和{@code y}，多次调用
* {@code x.equals（y）}始终返回{@code true}
*或一直返回{@code false}，提供否
*在{@code等}比较中使用的信息
*对象被修改。
* <li>对于任何非空引用值{@code x}，
* {@code x.equals（null）}应该返回{@code false}。
* </ ul>
* <p>
*类{@code Object}的{@code equals}方法实现
*对象上最可区别的可能的等价关系;
*就是对于任何非空参考值{@code x}和
* {@code y}，此方法返回{@code true}
*如果{@code x}和{@code y}引用相同的对象
*（{@code x == y}的值为{@code true}）。
* <p>
*请注意，通常需要覆盖{@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）;
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,444评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,421评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,036评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,363评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,460评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,502评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,511评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,280评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,736评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,014评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,190评论 1赞 342
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,848评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,531评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,159评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,411评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,067评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,078评论 2赞 352

推荐阅读更多精彩内容

  • HashMap的实现
    实际上，HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算...
    曹振华阅读 2,510评论 1赞 37
  • 我的帝都之行（长城）
    2017年8月5日，晴。今天的北京天气依旧炎热，然而酷暑高温却阻止不了我们爬长城的决心！ 北京是我...
    y有情有义阅读 396评论 0赞 1
  • 年度 For Face 总结
    自从爱美意识觉醒，经过一段时间的“买买买”后，我这个护肤和化妆小白终于也算是“摸着石头过了河”。鉴于最近“买买买”...
    YoYo_Bong阅读 419评论 0赞 1