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

作者: CodeJava | 来源:发表于2017-06-26 20:00 被阅读0次

来看例子

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-------------------------------------------------------------------------");

    }

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}.
* 
* 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 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.
* </ul>
* 
* 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.
* 
* The {@code equals} method implements an equivalence relation
* on non-null object references:
* <ul>
* <li>It is reflexive: for any non-null reference value
* {@code x}, {@code x.equals(x)} should return
* {@code true}.
* <li>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}.
* <li>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}.
* <li>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.
* <li>For any non-null reference value {@code x},
* {@code x.equals(null)} should return {@code false}.
* </ul>
* 
* 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}方法实现等价关系
*非空对象引用：
* <ul>
* <li>它是反身：对于任何非空参考值
* {@code x}，{@code x.equals（x）}应该返回
* {@code true}。
* <li>对于对称：对于任何非空引用值
* {@code x}和{@code y}，{@code x.equals（y）}
*只要返回{@code true}
* {@code y.equals（x）}返回{@code true}。
* <li>它是传递：对于任何非空参考值
* {@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> ：对于任何非空参考值
* {@code x}和{@code y}，多次调用
* {@code x.equals（y）}始终返回{@code true}
*或一直返回{@code false}，提供否
*在{@code等}比较中使用的信息
*对象被修改。
* <li>对于任何非空引用值{@code x}，
* {@code x.equals（null）}应该返回{@code false}。
* </ ul>
* 
*类{@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）;

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

HashSet实现是利用了HashMap去进行的比较看Add方法；利用了静态全局变量 Value为相同的值如果Key相同那么map中只有一个对象；我们再看HashMap的put方法。

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

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

HashSet实现是利用了HashMap去进行的比较 看Add方法 ； 利用了静态全局变量 Value为相同的值 如果Key相同那么map中只有一个对象 ； 我们再看HashMap的put方法。

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

HashSet实现是利用了HashMap去进行的比较看Add方法；利用了静态全局变量 Value为相同的值如果Key相同那么map中只有一个对象；我们再看HashMap的put方法。