Hash哈希（hashCode、HashSet 、HashMap）

2024-03-29 11:00:52

文章目录

Hash

Hash

哈希表基础：

hash函数：Index = hash(key)
1. 除留取余 ：index = key MOD p
2. 折叠法
3. 平方取中
4. …
哈希冲突
1. 开放定址
2. 链地址法
3. 再散列法

HashMap类

存储

HashMap使用的是 链地址法 解决 hash冲突。

计算hash值：hashCode()
冲突时候判断：equals()

数组 + 链表 + 红黑树

HashMap的长度

初始容量大小和每次扩充容量大小的不同：

创建时如果不指定容量初始值， Hashtable默认的初始大小为 11，之后每次扩充，容量变为原来的2n+1 。HashMap 默认的初始化大小为16 。之后每次扩充，容量变为原来的2倍。
创建时如果给定了容量初始值，那么Hashtable 会直接使⽤你给定的大小，而HashMap 会将其扩充为的幂次方大小（ HashMap 中的 tableSizeFor() ⽅法保证）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。

Why? 2 的幂次方：

为了能让 HashMap 存取⾼效，尽量较少碰撞，也就是要尽量把数据分配均匀。

Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得比较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。
这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。
长度取模： (n - 1) &hash 。 n总是为偶数，并且是16的倍数，16的二进制为 0001 0000, 16*1 = 15，15的二进制表示为0000 1111。当n要是2的幂次方时候，(n - 1) &hash 的方法可以得到 hash % n取余的结果，。
为什么不直接使用 hash % n？ & 的效率更高。

// java.util.HashMap 源码
// 主要功能是返回一个比给定整数大且最接近的2的幂次方整数，如给定10，返回2的4次方16. 
// 用来保证 容量初始值为2的幂次方整数.
    static final int tableSizeFor(int cap) { // 10;  0000 1010
        int n = cap - 1;// 9;  0000 1001
        n |= n >>> 1;   // 13;  0000 1001 | 0000 0100 = 0000 1101
        n |= n >>> 2;	// 15;  0000 1101 | 0000 0110 = 0000 1111
        n |= n >>> 4;	// 15;  0000 1111 | 0000 0111 = 0000 1111
        n |= n >>> 8;	// 15;  0000 1111 | 0000 0111 = 0000 1111
        n |= n >>> 16;	// 15;  0000 1111 | 0000 0111 = 0000 1111   
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    }

// java.util.HashMap 源码
    static final int hash(Object key) { // 获取hash值
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    // ----------------------------------------------------------------
    int index = (n - 1) & hash; // 长度取模

HashMap、ConcurrentHashMap 和 HashTable(弃用)

底层数据结构：
1. HashTable：数组 + 链表
2. HashMap、ConcurrentHashMap：JDK1.8之后，数组 + 链表 + 红黑树
线程安全：HashTable和ConcurrentHashMap
1. HashMap不保证线程安全；
2. Hashtable使用一把锁，同一时间段只能有一个线程进行操作。及其低效；
3. ConcurrentHashMap的并发控制使用synchronized和CAS实现。

全局锁

ConcurrentHashMap：JDK1.7 将数据一段一段的存储，每一个数据段分配一把锁(可重入锁)。Segment（实现可重入锁） + HashEntry（键值对存储）构成。

ConcurrentHashMap：JDK1.8 取消分段锁，使用CAS（Compare and Swap）和synchronized来保证线程安全。链表超过阈值( 8 ) 之后将链表转换为红黑树。

上图为转载图片原地址

引用文章
HashTable与HashMap区别
 ConcurrentHashMap实现原理及源码分析

hashCode()方法

	// Java 中java.lang.Object 类源码
    @HotSpotIntrinsicCandidate
    public native int hashCode();

int hashCode()是Object类中的方法，该方法直接返回该对象的地址；这表示若自定义的类若不对其进行重写，则会返回当前对象的地址。

hashCode() 与 equals() 的关联

情况1（不重写hashCode()和equals() 方法）

import java.util.HashMap;
class Key {
	private Integer id;
	public Integer getId()
   	{return id; }
   	public Key(Integer id)
   	{this.id = id;  }
  }
 
  public class WithoutHashCode {
      public static void main(String[] args) {
          Key k1 = new Key(1);
          Key k2 = new Key(1);
          HashMap<Key,String> hm = new HashMap<Key,String>();
          hm.put(k1, "Key with id is 1");    
          System.out.println(hm.get(k2));    
      }
  }

hashCode()是对应对象的地址，hm.get(k2)会失败。

情况2（仅仅重写hashCode()方法）

import java.util.HashMap;
class Key {
	private Integer id;
	public Integer getId()
   	{return id; }
   	public Key(Integer id)
   	{this.id = id;  }     
	public int hashCode()
 	{ return id.hashCode(); }
  }
 
  public class WithoutHashCode {
      public static void main(String[] args) {
          Key k1 = new Key(1);
          Key k2 = new Key(1);
          HashMap<Key,String> hm = new HashMap<Key,String>();
          hm.put(k1, "Key with id is 1");    
          System.out.println(hm.get(k2));    
      }
  }

hashCode()被重写返回的是id，k1、k2的id一致，但是hm.get(k2)仍然会失败。HashMap是用链地址法来处理冲突，也就是说，在id=1对应的hash值上，有可能存在着多个用链表形式存储的对象。

当我们通过k2的hashCode到id=1的hash值上查找时候，确实会得到k1。但k1有可能仅仅是和k2具有相同的hash值，但未必和k2相等（值可能不一样），这个时候，就需要调用Key对象的equals方法来判断两者是否相等。

如果不对equals()方法进行重写，则会调用Object的equals()方法，Object的equals()方法比较的是两个对象的地址。

情况3（重写hashCode()和equals() 方法）

import java.util.HashMap;
class Key {
	private Integer id;
	public Integer getId()
   	{return id; }
   	public Key(Integer id)
   	{this.id = id;  }
	public boolean equals(Object o) {
		if (o == null || !(o instanceof Key))
		{ return false; }
		else
        { return this.getId().equals(((Key) o).getId());}
	}
     
	public int hashCode()
 	{ return id.hashCode(); }
  }
 
  public class WithoutHashCode {
      public static void main(String[] args) {
          Key k1 = new Key(1);
          Key k2 = new Key(1);
          HashMap<Key,String> hm = new HashMap<Key,String>();
          hm.put(k1, "Key with id is 1");    
          System.out.println(hm.get(k2));    
      }
  }

重写hashCode()和equals() 方法。并且注意equals()方法的内容，是利用包装类的equals方法进行比较。

hm.get(k2)会返回："Key with id is 1"

// int包装类Integer的equals方法，直接进行值的比较
    public boolean equals(Object obj) {
        if (obj instanceof Integer) {
            return value == ((Integer)obj).intValue();
        }
        return false;
    }

== 符号: 基本数据类型比值，引用数据类型比"地址"

码农公寓