首頁 > 藝術
HashSet-基本使用
由 碼一碼程式碼 發表于 藝術2023-01-21
簡介2String類的hashCode
nyquist增補曲線怎麼畫
HashSet-基本使用
1。1 問題提問
1。3 問題解答
1
HashSet的特點
1
,
底層資料結構是雜湊表
特點:儲存快
2
,
不能保證儲存和取出的順序完全一致
3
,
沒有帶索引的方法
,
所以不能使用普通的for迴圈遍歷
4
,
set集合
元素唯一
5
,
不是執行緒安全的;
6
,
集合元素可以為
NULL
2
HashSet的基本使用是什麼
HashSet
<
String
>
set
=
new
HashSet
();
set
。
add
(
“123”
);
set
。
add
(
null
);
set
。
add
(
“124”
);
set
。
add
(
“aaa”
);
for
(
String
s
:
set
) {
System
。
out
。
println
(
s
);
}
列印結果
:
null
aaa
123
124
二 HashSet-雜湊值
1。1 問題提問
1
什麼是hash值
2
hash值的作用是什麼
1。3 問題解答
1
什麼是hash值
雜湊值
:(
雜湊碼值
):
是jdk根據物件的地址或者字串或者數字算出來的int型別的數值
>
是
一個十進位制的整數
2
hash值的作用是什麼
讓同一個類的物件按照自己不同的特徵儘量的有不同的雜湊值,
但不表示不同的物件雜湊碼完全不同。也有相同的情況,看程式設計師如何寫雜湊值的演算法。
1。4 案例
Object類中有一個方法可以獲取物件的雜湊值
//根據物件的地址值計算的
public
native
int
hashCode
();
//native 代表的呼叫的本地作業系統的方法
class
Person
{
int
age
;
String
name
;
public
Person
() {
}
public
Person
(
int
age
,
String
name
) {
this
。
age
=
age
;
this
。
name
=
name
;
}
}
public
static
void
main
(
String
[]
args
) {
Person
p1
=
new
Person
();
Person
p2
=
new
Person
();
//相同物件返回的雜湊碼值相同
System
。
out
。
println
(
p1
。
hashCode
());
//381259350
System
。
out
。
println
(
p1
。
hashCode
());
//381259350
//不同物件返回的雜湊碼值不同 因為呼叫的是Object類中的hashCode方法(透過的物件的地址值計算)
System
。
out
。
println
(
p2
。
hashCode
());
//2129789493
System
。
out
。
println
(
“————————————————————-”
);
/*
toString() 的原碼 this。getClass()。getName() + “@” + Integer。toHexString(this。hashCode());
16b98e56就是p1 雜湊碼值381259350的16進製表現形式
*/
System
。
out
。
println
(
p1
);
//com。demo11。Person@16b98e56
System
。
out
。
println
(
p2
);
//com。demo11。Person@7ef20235
System
。
out
。
println
(
p1
==
p2
);
//false
System
。
out
。
println
(
“————————————————————-”
);
String
s1
=
new
String
(
“abc”
);
String
s2
=
new
String
(
“abc”
);
//字串也重寫了hashCode方法所以內容相同返回的是相同的雜湊值
System
。
out
。
println
(
s1
。
hashCode
());
//96354
System
。
out
。
println
(
s2
。
hashCode
());
//96354
System
。
out
。
println
(
“————————————————————-”
);
//我們希望保證的是相同的物件返回的是相同的雜湊值 不同物件儘量返回不同的雜湊值 但是也不能保證不同物件一定返回的是不同的雜湊值
System
。
out
。
println
(
“重地”
。
hashCode
());
//1179395
System
。
out
。
println
(
“通話”
。
hashCode
());
//1179395
System
。
out
。
println
(
“————————————————————-”
);
//其實我們認為內容相同就P3和P4是同一個物件 就應該讓他們返回相同的雜湊值
Person
p3
=
new
Person
(
18
,
“壯壯”
);
Person
p4
=
new
Person
(
18
,
“壯壯”
);
System
。
out
。
println
(
p3
。
hashCode
());
//668386784
System
。
out
。
println
(
p4
。
hashCode
());
//1329552164
Integer
i
=
new
Integer
(
100
);
System
。
out
。
println
(
i
。
hashCode
());
//100
}
//讓內容相同的物件返回相同的雜湊值 要重寫hashCode方法
@Override
public
int
hashCode
() {
//如果name為空不做判斷直接寫hashCode()會報空指標異常
return
age
+
(
name
==
null
?
0
:
name
。
hashCode
());
}
//這樣P3和P4就能返回相同的雜湊碼了
//但是這樣做會出現物件內容不同但是雜湊值相同的情況
//所以自己寫的比較low儘量少出現這種情況
p1
name
。
hashCode
()
=
44
;
age
=
20
hash
=
64
p2
name
。
hashCode
()
=
20
;
age
=
44
hash
=
64
雖然內容不同
但是經過計算只有得到的hash值相同了
/
系統幫你重寫的
@Override
//減少衝突
public
int
hashCode
() {
int
result
=
age
;
result
=
31
*
result
+
(
name
!=
null
?
name
。
hashCode
() :
0
);
return
result
;
}
//小知識:31這個數字的用意
1
選擇係數的時候儘量選擇大的
,
因為計算出的hash地址越大
,
所謂的衝突就會越少
2
31
是5Bits
相乘造成的資料溢位機率小
3
31
是
i
*
31
==
(
i
<<
5
)
-
1
來表示
提高演算法效率
,
很多虛擬機器中都有相關的最佳化
4
31
是個素數
能夠使得它和其他數相乘後得到的結果比其他方式更容易產成唯一性
//注意點:
Hash值應該符合什麼原則
1
等冪性
,
不管執行多少次獲取Hash值的操作
,
只要物件不變
,
那麼Hash值是固定的。
2
對等性。若兩個物件equal方法返回為true,則其hash值也應該是一樣的。
3
互異性。若兩個物件equal方法返回為false,則其hash值最好也是不同的,但這個不是必須的,只是這樣做
會提高hash類操作的效能(碰撞機率低)。
常見的雜湊碼的演算法有:
1
Object類的hashCode
。
返回物件的記憶體地址經過處理後的結果,由於每個物件的記憶體地址都不一樣,所以
雜湊碼也不一樣。
2
String類的hashCode
。
根據String類包含的字串的內容,根據一種特殊演算法返回雜湊碼,只要字串內
容相同,返回的雜湊碼也相同。
3
Integer類,返回的雜湊碼就是Integer物件裡所包含的那個整數的數值,由此可見,2個一樣大小的
Integer物件,返回的雜湊碼也一樣。
1。5 HashSet如何儲存儲存內容相同的物件
HashSet
新增元素,首先比較hash值
是否有相同hash,沒有則新增成功,有則繼續比較equals,如果不同則新增成功,否則不新增。
class
Person
{
int
age
;
int
number
;
public
Person
(
int
age
,
int
number
) {
this
。
age
=
age
;
this
。
number
=
number
;
}
@Override
//可以先不寫
public
boolean
equals
(
Object
o
) {
return
true
;
}
@Override
public
int
hashCode
() {
return
age
+
number
;
}
@Override
public
String
toString
() {
return
“Person{”
+
“age=”
+
age
+
“, number=”
+
number
+
‘}’
;
}
}
public
static
void
main
(
String
[]
args
) {
Person
p1
=
new
Person
(
18
,
20
);
Person
p2
=
new
Person
(
20
,
18
);
System
。
out
。
println
(
p1
。
hashCode
());
System
。
out
。
println
(
p2
。
hashCode
());
Set
set
=
new
HashSet
();
set
。
add
(
p1
);
set
。
add
(
p2
);
//如果不重寫equals 返回全部為true 則這兩個都能新增成功
//否則只能新增一個成功
for
(
Object
o
:
set
) {
System
。
out
。
println
(
o
);
}
}
三 HashSet-JDK7底層原理解析
1。1 問題提問
1
HashSet集合儲存資料的結構是什麼
2
jdk1
。
8
之前用的是什麼資料結構
3
jdk1
。
8
之後
(
包括1
。
8
)
用的是什麼資料結構
1。3 問題解答
1
HashSet集合儲存資料的結構是什麼
HashSet集合儲存資料的結構
(
雜湊表
:
速度快
)
2
jdk1
。
8
之前用的是什麼資料結構
jdk1
。
8
之前
,
雜湊表
=
陣列
+
連結串列
(
使用連結串列處理衝突
)
3
jdk1
。
8
之後
(
包括1
。
8
)
用的是什麼資料結構
jdk1
。
8
之後
,
雜湊表
=
陣列
+
連結串列
+
紅黑樹
(
提高查詢的速度
)
1。4 補充
7
採用頭插法
新資料在第一個
8
採用尾插法
新資料在原資料之後
1
陣列預設長度是16
載入因子是0
。
75
當存到16
*
0。75
=
12
個元素的時候會發生擴容
,
為原陣列長度的兩倍
2
獲取要存入元素的hash值透過演算法計算出該元素應該存入的陣列索引位置
如果該位置為null
直接新增
如果該位置不是null
則與連結串列的中的所有元素
透過equals方法比較內容
(
屬性值
)
如果和連結串列中的某一個元素內容相同
,
表示是同一個元素
不存
如果都不一樣
存入集合掛載到該連結串列上