2、哈希表

2.1、哈希冲突

冲突位置，把数据构建为链表结构。

装载因子=哈希表中的元素个数 / （散列表）哈希表的长度

装载因子越大，说明链表越长，性能就越低，那么哈希表就需要扩容，把数据迁移到新的哈希表中！

数据会经过两层比较：

一个是对哈希值的比较 使用hashcode（）方法

另一个是对key值的比较，使用equals（）方法

如果两个对象相同，hashcode一定相同。
但是hashcode相同，两个对象不一定相同。

哈希冲突是指，不同的key经由哈希函数，映射到了相同的位置上，造成的冲突。

/**
 * @author Administrator
 * @date 2022-09-09 14:28
 */
public class MyHashTable<K,V> {
	private Node<K, V>[] table;    // 实例化一个Node数组 Node数组本身又是个链表

	private static class Node<K,V>{
		final int hash; //hash值
		final K key;    
		V value;
		Node<K,V> next; //下一个节点 kv对

		public Node(int hash, K key, V value, Node<K, V> next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}

	public MyHashTable(int capacity) {
		table = (Node<K,V>[]) new Node[capacity];
	}
	public void put (K key,V value){
		// 1. 计算哈希值
		int hash = hash(key);
		// 2. 计算数组的索引值
		int i = (table.length-1) & hash;
		// 3. 把当前的kv对 存到Node里
		Node<K,V> node = new Node (hash,key,value,null);
		// 4. 根据索引下标 拿到目前table里的数据 然后进行对比
		Node<K,V> kvNode = table[i];

		if(kvNode == null ){
			// 如果为空 则说明当前位置没有数据 可以直接存
			table[i] = node;
			return;
		}
		// 如果有值 就去看 key是否一样
		if(kvNode.key.equals(key))
		{
			//  如果一样 就覆盖
			kvNode.value = value;
		}
		else{
			// 如果不一样就用链表存起来
			kvNode.next = node;
		}
	}
	public V get (K key){
		int hash = hash(key);
		int i = (table.length - 1 ) & hash;
		Node<K,V> node = table[i];
		if(node == null)
		{
			return null;
		}
		Node<K,V> newNode = node;      // 做条件判断
		// 如果存在这个值 而且存在hash冲突 那就需要去循环这个链表 直到找到那个key
		while (node.next != null)
		{
			if (newNode.key.equals(key)){
				// 这就说明找到了 直接跳出循环
				break;
			}else{
				newNode=newNode.next;   // 如果找不到key 就一直往链表的后面找
			}
		}
		return newNode.value;       // 最后返回这个值
	}

	/**
	 * 计算哈希值
	 * @param key
	 * @return
	 */
	static final int hash(Object key){
		int h;
		return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
	}

	public static void main(String[] args) {
		MyHashTable<String,String> hashTable = new MyHashTable<String, String>(5);
		hashTable.put("key1","ycw");
		hashTable.put("key2","ycw2");
		hashTable.put("key1","ycw3");
		System.out.println(hashTable.get("key1"));
		System.out.println(hashTable.get("key2"));
	}
}

2.2、hashmap

扩容

​ 在填装因子(loaderFactor) > 0.75 时进行扩容

1. 创建新的数组，长度newLength是原来的2倍（将哈希表的存储空间增加为原来的两倍）。
2. 遍历旧列表中取出元素的key之后，重新进行hash计算 newndex = (newLength- 1) & hash。
3. 重新插入元素。