目录介绍
-
1.Hash的作用介绍
- 1.1 Hash的定义
- 1.2 Hash函数特性
- 1.3 Hash的使用场景
-
2.如何判断两个对象相等
- 2.1 判断两个字符串
- 2.2 判断两个int数值
- 2.3 其他基本类型
-
3.HashCode深入分析
- 3.0 HashCode是什么
- 3.1 为什么要重写HashCode
- 3.2 HashCode源代码分析
- 3.3 HashCode带来的疑问
- 3.4 HashCode的作用
- 3.5 HashMap中的HashCode
- 3.6 可直接用hashcode判断两个对象是否相等
-
4.Hash表是什么
- 4.1 Hash表定义
- 4.2 Hash表简单介绍
-
5.Hash中的算法应用
- 5.1 基础算法
- 5.2 经典算法[摘自网络]
- 5.3 Hash碰撞[摘自网络]
-
6.Hash在Java中的应用场景
- 6.1 equals与hashCode有两个注意点
- 6.2 以HashSet为例说明hashCode()的作用
- 6.3 以HashMap为例说明Hash的作用
- 6.4
- 7.版本更新情况
- 8.其他介绍
1.Hash的作用介绍
1.1 Hash的定义
-
散列（哈希）函数
- 把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值，是一种压缩映射。
- 或者说一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
1.2 Hash函数特性
1.3 Hash的使用场景
- 比如说我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件就是我们所需要的呢？我们不可能去一一检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息，这时候，就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。
- 散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。
- 这种标志有何意义呢？之前文件下载过程就是一个很好的例子，事实上，现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。
2.如何判断两个对象相等
2.1 判断两个字符串
String a = "yc1";
String b = "yc2";
boolean isEqual = a.equals(b);
- 当然Object的子类可以通过重写equals的方法，实现子类自身的对象是否相等的逻辑；String是Object的子类，查看下它的equals方法
//在Object类中
public boolean equals(Object obj) {
//直接比较的是地址
return (this == obj);
}
//在String类中
public boolean equals(Object anObject) {
//直接比较的是地址
if (this == anObject) {
return true;
}
//盘旋是否是字符串String类型
if (anObject instanceof String) {
String anotherString = (String) anObject;
int n = count;
if (n == anotherString.count) {
int i = 0;
//循环判断每个字符是否相等
while (n-- != 0) {
if (charAt(i) != anotherString.charAt(i))
return false;
i++;
}
return true;
}
}
return false;
}
2.2 判断两个int数值
- Integer类的equals方法又是如何实现的呢？
Integer a = Integer.valueOf("1");
Integer b = Integer.valueOf("2");
boolean ab = a.equals(b);
public boolean equals(Object obj) {
//先判断是否是Integer类型
if (obj instanceof Integer) {
//转为int值后进行比较
return value == ((Integer)obj).intValue();
}
return false;
}
2.3 其他基本类型
//short类型
@Override
public int hashCode() {
return Short.hashCode(value);
}
public static int hashCode(short value) {
return (int)value;
}
//Byte类型
@Override
public int hashCode() {
return Byte.hashCode(value);
}
public static int hashCode(byte value) {
return (int)value;
}
//Long类型
@Override
public int hashCode() {
return Long.hashCode(value);
}
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
//long类型作为索引范围太大，需要转为int类型。这里简单的获取低32位容易导致散列不均，因为高位部分没有被利用。所以这里采用逻辑右移32位，让高32位和低32位进行XOR操作，导致高位低位都能被利用到
//Boolean类型
@Override
public int hashCode() {
return Boolean.hashCode(value);
}
public static int hashCode(boolean value) {
return value ? 1231 : 1237;
}
//采用两个质数作为true或false的索引。这两个质数足够大，用来作为索引时，出现碰撞的可能性低。
3.HashCode深入分析
3.0 HashCode是什么
- HashCode是Object的一个方法，hashCode方法返回一个hash code值，且这个方法是为了更好的支持hash表，比如String，Set，HashTable、HashMap等;
3.1 为什么要重写HashCode
- 如果用 equal 去比较的话，如果存在1000个元素，你 new 一个新的元素出来，需要去调用1000次equal去逐个和他们比较是否是同一个对象，这样会大大降低效率。hashcode实际上是返回对象的存储地址，如果这个位置上没有元素，就把元素直接存储在上面，如果这个位置上已经存在元素，这个时候才去调用equal方法与新元素进行比较，相同的话就不存了，散列到其他地址上
3.2 HashCode源代码分析
public int hashCode() {
int lockWord = shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
//返回的是对象引用地址
return System.identityHashCode(this);
}
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
for (int i = 0; i < count; i++) {
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
public int hashCode() {
//int值
return value;
}
3.3 HashCode带来的疑问
- 为何重写equals建议同时重写hashCode？
- hashCode是什么？
- hashCode作用？
- hash code（hash值）是什么？
- hash table（hash表）是什么？
- hashCode方法对hash表有益处？
- hashCode方法对不是hash有益处吗?
3.4 HashCode的作用
-
减少查找次数，提高程序效率
-
例如查找是否存在重复值
- h(k1)≠h(k2)则k1≠k2
- 首先查看h(k2)输出值（内存地址），查看该内存地址是否存在值；
- 如果无，则表示该值不存在重复值；
- 如果有，则进行值比较，相同则表示该值已经存在散列列表中，如果不相同则再进行一个一个值比较；而无需一开始就一个一个值的比较，减少了查找次数
3.5 HashMap中的HashCode
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.6 可直接用hashcode判断两个对象是否相等
4.Hash表是什么
4.1 Hash表定义
- 根据关键码值（KEY-VALUE）而直接进行访问的数据结构；它通过把关键码值（KEY-VALUE）映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
4.2 Hash表简单介绍
- 将k作为输入值，h(k)输出值作为内存地址，该内存地址用来存放value，然后可以通过k获取到value存放的地址，从而获取value信息。
5.Hash中的算法应用
5.1 基础算法
- 比如，Java中的String.hashCode使用乘法和加法
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
for (int i = 0; i < count; i++) {
//乘法与加法
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
5.2 经典算法[摘自网络]
5.3 Hash碰撞[摘自网络]
- hash是存在碰撞的，如果k1≠k2，h(k1)=h(k2) 则发生碰撞；
6.Hash在Java中的应用场景
6.1 equals与hashCode有两个注意点
6.2 以HashSet为例说明hashCode()的作用
6.3 以HashMap为例说明Hash的作用
//put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//上面这几个方法都用到了这个方法
static final int hash(Object key) {
int h;
//计算hashCode，并无符号移动到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
举个例子: h = 363771819^(363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)
这样做可以实现了高地位更加均匀地混到一起
参考博客
关于其他内容介绍
01.关于博客汇总链接
02.关于我的博客
