來(lái)看例子
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));
}
運(yùn)行結(jié)果
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));
}
運(yùn)行結(jié)果
97
97
false
true
對(duì)比
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));
}
運(yùn)行結(jié)果
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);
}
}
運(yùn)行結(jié)果
set.size()===1 ; object==a
在Set里面認(rèn)為對(duì)象相等。
HashSet實(shí)現(xiàn)是利用了HashMap去進(jìn)行的比較 看Add方法 郭变； 利用了靜態(tài)全局變量 Value為相同的值 如果Key相同那么map中只有一個(gè)對(duì)象 颜价； 我們?cè)倏碒ashMap的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上場(chǎng) 诉濒， HashMap有多個(gè)版本周伦，Android中的不同版本JDK24和JDK25不同
初始化容量也不同 不是我們看到的Java的16.
Java7和Java8的也不同 Java8用到紅黑樹(shù)等 默認(rèn)的擴(kuò)容因子還都是0.75
版本對(duì)比先不比較，比較了一個(gè)晚上都凌亂了未荒。
HashMap put方法源碼
先看AndroidSDK 25版本中的HashMap源碼
自己點(diǎn)進(jìn)去看一下专挪。我們利用反射先看看初始化的屬性
HashMap 網(wǎng)上原理一大堆沒(méi)看一次，大有受益又有疑問(wèn)，
實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)寨腔，我們來(lái)實(shí)踐一下速侈。
我們采用實(shí)踐通過(guò)實(shí)踐看原理
先建一個(gè)空的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("是數(shù)組："+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-------------------------------------------------------------------------");
}
}
然后我們看到各種的初始化的值 對(duì)于static final的不會(huì)改變 以后就不再打印
I/System.out: transient [Ljava.util.HashMap$HashMapEntry; table == [Ljava.util.HashMap$HashMapEntry;@6ca7431
這個(gè)是數(shù)組。
不會(huì)變化的 記住就行
static final int DEFAULT_INITIAL_CAPACITY = 4; //默認(rèn)初始化容量
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認(rèn)擴(kuò)容因子
static final HashMapEntry<?,?>[] EMPTY_TABLE = {}; //空的數(shù)組
final float loadFactor = DEFAULT_LOAD_FACTOR; //默認(rèn)擴(kuò)容因子
會(huì)變化的變量
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
transient int size; //是hashmap的元素個(gè)數(shù)
int threshold; //臨界值;
transient int modCount; //修改次數(shù)
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: 是數(shù)組：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: 是數(shù)組：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-------------------------------------------------------------------------
再來(lái)一個(gè)方法只打印變化的量 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);
初始化數(shù)據(jù) entrySet == null table.length == 0 modCount == 0 sise == 0 threshold == 4; //臨界值
分別添加1個(gè)數(shù)據(jù)和添加兩個(gè)數(shù)據(jù)發(fā)生了哪些變化
添加1數(shù)據(jù) entrySet == null table.length == 4 modCount == 1 size == 1 threshold == 3倚搬；
添加2數(shù)據(jù) 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-------------------------------------------------------------------------
我們直接制作輸成表格 改造下的代碼 這是 擴(kuò)容的規(guī)律乾蛤，思考一下 負(fù)載因子是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的負(fù)載因子每界，并且明確忽略所選值。
并且Android中嚴(yán)格使用0.75 其他的輸入的 值直接忽略掉家卖，所以只能更改初始值tabled的長(zhǎng)度眨层。負(fù)載因子不能改變
無(wú)論輸入0.5和0.2還是0.9都不起作用。
其中方法的演化在后面inflateTable(threshold); 和 里面的
int capacity = roundUpToPowerOf2(toSize);
Integer.highestOneBit(number) 和 (Integer.bitCount(number)
這幾個(gè)方法在后面推導(dǎo)
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時(shí)篡九。
transient HashMapEntry<K,V>[] table
初始化數(shù)據(jù) entrySet == null table.length == 0 modCount == 0 sise == 0 threshold == 4;
// threshold 臨界值
第一次put時(shí)一個(gè)值時(shí)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
會(huì)初始化確定一個(gè)值HashMapEntry<K,V>[] table 長(zhǎng)度谐岁，這里table.length==4
I: | entrySet == null | modCount == 1 | size == 1 | table.length==4 | threshold == 3 |
if (key == null)
return putForNullKey(value);
如果為空就調(diào)用這個(gè) 并返回HashMap允許空key值為空。
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
然后根據(jù)key 拿到 hash值榛臼。
int i = indexFor(hash, table.length); 然后根據(jù)Hash值和當(dāng)前table的長(zhǎng)度
看上面table.length 為二倍擴(kuò)容 所以為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);
}
這個(gè)算法int h為hashcode int類型 int length 為 2的次方得到結(jié)果
length == 4 length - 1 = 3 得到的值也為0123伊佃，0123，循環(huán)
length == 8 length - 1 = 7 得到的值也為01234567沛善，01234567航揉，循環(huán)
StringBuilder stringBuffer = new StringBuilder();
for (int i = 0; i < 10000; i++) {
stringBuffer.append(i & 3).append(",");
}
System.out.println(stringBuffer.toString());
結(jié)果
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 時(shí) 結(jié)果
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
就會(huì)得到小于數(shù)組長(zhǎng)度的一個(gè)i值。
然后遍歷數(shù)組金刁，
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
放入四個(gè)數(shù)帅涂，此時(shí)table.length = 4
hashcode各不相同，但是int i = indexFor(int h, int length) 里面卻有重復(fù)
map.put("0","a"); e = table[0] 此時(shí) e == null 走下面的
addEntry(hash, key, value, i); 方法 發(fā)現(xiàn)條件不滿足擴(kuò)容就執(zhí)行下面的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);
}
執(zhí)行createEntry方法媳友。 此時(shí)創(chuàng)建了一個(gè)對(duì)象。
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++;
}
先拿到當(dāng)前位置的對(duì)象是第一次此時(shí)為null 先臨時(shí)變量記錄下來(lái)
HashMapEntry<K,V> e = table[bucketIndex];
然后當(dāng)前位置的數(shù)組指向新創(chuàng)建的對(duì)象产捞，并將 hash值 key值 value值醇锚，和剛才被替換掉的對(duì)象記錄下來(lái)。
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");
此時(shí) "4".hash==1342561432 ; table.legth == 4 ;
i= "4".hash & 3 == 0
在 e = table[0] 已經(jīng)存在了一個(gè)值坯临。 此時(shí) e != null 那么進(jìn)入for循環(huán)進(jìn)行判斷
e = table[0] = new HashMapEntry(-554176856, "0","a",null);
此時(shí)兩個(gè)在一個(gè)數(shù)組位置上焊唬，開(kāi)始判斷是替換此鏈表的位置還是再后面添加一個(gè)？
發(fā)現(xiàn) 此時(shí) 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
此時(shí)跳出循環(huán) 繼續(xù)創(chuàng)建 那么 按上面的流程
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] 鏈表上兩個(gè)值看靠。
table[0] = new HashMapEntry(1342561432, "4","a", new HashMapEntry( -554176856, "0","a",null) )
如果map.put("4","a"); 換成 如果map.put("0","b");
此時(shí)已然是table[0]上進(jìn)行操作 并且hashe相同進(jìn)入循環(huán)
e.hash == -554176856 ; e.hash == hash = true
并且 由于key為字符串 那么((k = e.key) == key 為T(mén)rue
此時(shí)進(jìn)行替換Value操作
table[0] next = new HashMapEntry(-554176856, "0","b",null);
加入Key不為字符串 Hashcode相同 ((k = e.key) == key不相同此時(shí)就要進(jìn)行 || equals比較啦赶促。
hashcode 為 int 類型 其中 字符串的數(shù)量一定大于int類型的數(shù)量
因此兩個(gè)對(duì)象就存在hashcode相等的時(shí)候，此時(shí)我們用==號(hào)比較地址挟炬，地址相同一定是同一個(gè)對(duì)象鸥滨。
這時(shí)假如我們表示去重操作嗦哆，兩個(gè)學(xué)生名字，學(xué)號(hào)一樣爵赵，我們認(rèn)為一個(gè)學(xué)生吝秕。我們?cè)趦?nèi)存中創(chuàng)建了兩個(gè)，那么怎么表示使用equals方法比較對(duì)相關(guān)的相等空幻，就去重寫(xiě)equals方法
學(xué)號(hào)相等 和 姓名相等就返回true 此時(shí)烁峭，他們的equals相等了。進(jìn)行判斷沒(méi)有錯(cuò)秕铛。
即使他們的hasecode不相等约郁，
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 看這行代碼也是成立的，會(huì)替換原有的值但两。
那么問(wèn)題發(fā)生的真正原因是什么呢鬓梅？
我們來(lái)看個(gè)例子吧。
此時(shí)我們重寫(xiě)equals 不重寫(xiě)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));
運(yùn)行結(jié)果： D/TAG: true
運(yùn)行結(jié)果 是相等的谨湘。 其他任何地方也是相等的 equals 具有對(duì)稱性 自反性 等等
那么我們看HashMap里面卻不認(rèn)可绽快，不給k賦值了，一個(gè)為null 另一個(gè)是真實(shí)的對(duì)象紧阔，放入其中認(rèn)為是兩個(gè)對(duì)象坊罢。
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());
運(yùn)行結(jié)果： D/TAG: hashMap.size()==2
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
再來(lái)看這句話 || key.equals(k) 認(rèn)為相等可以替換啊，那么為啥不讓會(huì)出現(xiàn)兩個(gè)擅耽。
student@4841 code 1617119160 table[0]
student@4842 code -35303204 table[0]
student@4843 code -2050440646 table[2]
student@4840 code 1439680537 table[1]
此時(shí)兩個(gè)對(duì)象即使發(fā)生在同一維數(shù)組上
因?yàn)?hasecode不相等那么 ((k = student) == student1沒(méi)有執(zhí)行 也就是 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", "結(jié)束" + k);
D/TAG: 結(jié)束null
hashCode方法可以這樣理解：它返回的就是根據(jù)對(duì)象的內(nèi)存地址換算出的一個(gè)值
hashmap中認(rèn)為活孩，hashCode不相等，兩個(gè)對(duì)象就不一樣乖仇。 這才是要害憾儒。
所以我們使用hashmap不得不重寫(xiě)hashcode
那么假如我們有無(wú)限大的內(nèi)存，無(wú)窮多個(gè)對(duì)象乃沙，那么他們中間HashCode總有相等的吧起趾。
if (true && ((k = student) == student1 || student1.equals(k))) {
Log.d("TAG", "" + k);
}
此時(shí)即使(k = student) == student1為false 那么 還有equals 就認(rèn)為是一個(gè)對(duì)象了。
是Hashcode重復(fù)了警儒， equals里面還比較了類名阳掐，屬性值。
所以當(dāng)我們認(rèn)為兩個(gè)對(duì)象相等時(shí)既要重寫(xiě)equals 又要 重寫(xiě)HashCode
看看Object里面的解釋冷蚂。
*返回對(duì)象的哈希碼值。這個(gè)方法是
*支持哈希表的利益汛闸，如提供的哈希表 {@link java.util.HashMap}{@code hashCode}的一般合同是： <li>無(wú)論何時(shí)在同一個(gè)對(duì)象上調(diào)用多次執(zhí)行Java應(yīng)用程序蝙茶，{@code hashCode}方法必須始終返回相同的整數(shù)，沒(méi)有提供任何信息用于{@code equals}對(duì)象的比較被修改诸老。這個(gè)整數(shù)不需要從一個(gè)執(zhí)行中保持一致應(yīng)用于另一個(gè)執(zhí)行相同的應(yīng)用程序隆夯。<li>如果兩個(gè)對(duì)象根據(jù){@code equals（Object）}相等钳恕，方法，然后在每個(gè)方法上調(diào)用{@code hashCode}方法兩個(gè)對(duì)象必須產(chǎn)生相同的整數(shù)結(jié)果蹄衷。<li>這是<em>不</ em>要求忧额，如果兩個(gè)對(duì)象不相等根據(jù){@link java.lang.Object＃equals（java.lang.Object）}方法，然后在每個(gè)方法上調(diào)用{@code hashCode}方法兩個(gè)對(duì)象必須產(chǎn)生不同的整數(shù)結(jié)果愧口。但是睦番，那程序員應(yīng)該知道產(chǎn)生不同的整數(shù)結(jié)果對(duì)于不相等的對(duì)象可能會(huì)提高散列表的性能。盡可能多的合理實(shí)用耍属，hashCode方法定義class {@code Object}確實(shí)返回不同的整數(shù)對(duì)象托嚣。 （這通常通過(guò)轉(zhuǎn)換內(nèi)部來(lái)實(shí)現(xiàn)將對(duì)象的地址變成一個(gè)整數(shù)，但這個(gè)實(shí)現(xiàn)技術(shù)是不需要的Java＆trade;編程語(yǔ)言厚骗。）@see java.lang.Object＃equals（java.lang.Object）
@see java.lang.System＃identityHashCode
equals 非空調(diào)用
對(duì)稱性
傳遞性
自己是自己的反身
盜一張結(jié)構(gòu)圖吧示启。
JDK8用的紅黑樹(shù) 再來(lái)一張
搞了一天一夜×旖ⅲ看也看累了吧夫嗓。
來(lái)張美女提提神
下面是擴(kuò)容相關(guān)方法。
在put里面數(shù)據(jù)冲秽， table的長(zhǎng)度根據(jù)threshold閥值舍咖，如上圖表格所示以二倍容量擴(kuò)容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
這個(gè)方法初始化時(shí)，因?yàn)?這個(gè)定義劳跃， 返回一個(gè)會(huì)給table設(shè)定一個(gè)長(zhǎng)度谎仲，默認(rèn)不輸入的化就是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];
}
這個(gè)方法比較繞也是醉了。 改寫(xiě)一下吧
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;
}
改寫(xiě)之后
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)這個(gè)方法的執(zhí)行執(zhí)行規(guī)律是
-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 為零時(shí) 為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);
}
簡(jiǎn)單的說(shuō)法
如果一個(gè)數(shù)是0, 則返回0刨仑；
如果是負(fù)數(shù), 則返回 -2147483648：【1000,0000,0000,0000,0000,0000,0000,0000】(二進(jìn)制表示的數(shù))郑诺；
如果是正數(shù), 返回的則是跟它最靠近的比它小的2的N次方
比如 17：
二進(jìn)制是【0000,0000,0000,0000,0000,0000,0001,0001】
highestOneBit(17)返回的是最高位的1個(gè)1, 其它全是0 的二進(jìn)制數(shù)：【0000,0000,0000,0000,0000,0000,0001,0000】，其實(shí)就是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
這時(shí)所有的負(fù)值全部轉(zhuǎn)化成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
.
這個(gè)方法有其精妙之處辙诞，可以多百度一下。
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版本中初始化長(zhǎng)度為 4 >>> 1 = 2
private static final int MINIMUM_CAPACITY = 4;
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
AndroidSDK25 初始化列表長(zhǎng)度是4
AndroidSDK24 hash值得來(lái)源也不一樣
int hash = Collections.secondaryHash(key);
AndroidSDK25 hash值得來(lái)源也不一樣
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();
/ **
*返回對(duì)象的哈希碼值飞涂。這個(gè)方法是
*支持哈希表的利益，如提供的哈希表
* {@link java.util.HashMap}祈搜。
* <p>
* {@code hashCode}的一般合同是：
* <ul>
* <li>無(wú)論何時(shí)在同一個(gè)對(duì)象上調(diào)用多次
*執(zhí)行Java應(yīng)用程序较店，{@code hashCode}方法
*必須始終返回相同的整數(shù)，沒(méi)有提供任何信息
*用于{@code equals}對(duì)象的比較被修改容燕。
*這個(gè)整數(shù)不需要從一個(gè)執(zhí)行中保持一致
*應(yīng)用于另一個(gè)執(zhí)行相同的應(yīng)用程序梁呈。
* <li>如果兩個(gè)對(duì)象根據(jù){@code equals（Object）}相等，
*方法蘸秘，然后在每個(gè)方法上調(diào)用{@code hashCode}方法
*兩個(gè)對(duì)象必須產(chǎn)生相同的整數(shù)結(jié)果官卡。
* <li>這是<em>不</ em>要求蝗茁，如果兩個(gè)對(duì)象不相等
*根據(jù){@link java.lang.Object＃equals（java.lang.Object）}
*方法，然后在每個(gè)方法上調(diào)用{@code hashCode}方法
*兩個(gè)對(duì)象必須產(chǎn)生不同的整數(shù)結(jié)果寻咒。但是哮翘，那
*程序員應(yīng)該知道產(chǎn)生不同的整數(shù)結(jié)果
*對(duì)于不相等的對(duì)象可能會(huì)提高散列表的性能。
* </ ul>
* <p>
*盡可能多的合理實(shí)用毛秘，hashCode方法定義
* class {@code Object}確實(shí)返回不同的整數(shù)
*對(duì)象饭寺。 （這通常通過(guò)轉(zhuǎn)換內(nèi)部來(lái)實(shí)現(xiàn)
*將對(duì)象的地址變成一個(gè)整數(shù)，但這個(gè)實(shí)現(xiàn)
*技術(shù)是不需要的
Java＆trade;編程語(yǔ)言熔脂。）
*
* @返回此對(duì)象的哈希碼值佩研。
* @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);
}
/ **
*表示某個(gè)其他對(duì)象是否等于此。
* <p>
* {@code equals}方法實(shí)現(xiàn)等價(jià)關(guān)系
*非空對(duì)象引用：
* <ul>
* <li>它是<i>反身</ i>：對(duì)于任何非空參考值
* {@code x}霞揉，{@code x.equals（x）}應(yīng)該返回
* {@code true}旬薯。
* <li>對(duì)于<i>對(duì)稱</ i>：對(duì)于任何非空引用值
* {@code x}和{@code y}，{@code x.equals（y）}
*只要返回{@code true}
* {@code y.equals（x）}返回{@code true}适秩。
* <li>它是<i>傳遞</ i>：對(duì)于任何非空參考值
* {@code x}绊序，{@code y}和{@code z}，if
* {@code x.equals（y）}返回{@code true}和
* {@code y.equals（z）}返回{@code true}秽荞，然后
* {@code x.equals（z）}應(yīng)該返回{@code true}骤公。
* <li> <i> <i> </ i>：對(duì)于任何非空參考值
* {@code x}和{@code y}，多次調(diào)用
* {@code x.equals（y）}始終返回{@code true}
*或一直返回{@code false}扬跋，提供否
*在{@code等}比較中使用的信息
*對(duì)象被修改阶捆。
* <li>對(duì)于任何非空引用值{@code x}，
* {@code x.equals（null）}應(yīng)該返回{@code false}钦听。
* </ ul>
* <p>
*類{@code Object}的{@code equals}方法實(shí)現(xiàn)
*對(duì)象上最可區(qū)別的可能的等價(jià)關(guān)系;
*就是對(duì)于任何非空參考值{@code x}和
* {@code y}洒试，此方法返回{@code true}
*如果{@code x}和{@code y}引用相同的對(duì)象
*（{@code x == y}的值為{@code true}）。
* <p>
*請(qǐng)注意朴上，通常需要覆蓋{@code hashCode}
*方法垒棋，只要這個(gè)方法被覆蓋，以便維護(hù)
* {@code hashCode}方法的一般合同痪宰，其中規(guī)定
*相等的對(duì)象必須具有相等的哈希碼叼架。
*
* @param obj要與之比較的引用對(duì)象。
* @return {@code true}如果此對(duì)象與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);
/**
*返回與給定對(duì)象相同的哈希碼
*將由默認(rèn)方法hashCode（）返回乖订，
*給定對(duì)象的類是否覆蓋
* hashCode（）。
*空引用的哈希碼為零具练。
*
*要為其計(jì)算hashCode的@param x對(duì)象
* @返回hashCode
* @since JDK1.1
*/
public static native int identityHashCode（Object x）;