java开放地址法和链地址法解决hash冲突

- 日理万妓 2023-10-18 14:10 121阅读 0赞

**hashMap对各位小伙们来说，没有不知道的了，使用过的人想必或多或少的都了解一点hashMap的底层实现原理，总结来说就是，数组+链表，至于源码的实现，大家可参看源码，今天想说的是hashMap是怎么解决hash冲突的呢？**

首先看一张图，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]

从这张图也大概可以看出来，hashMap维护的是一个数组，数组里面的每个单元又是一个个链表，那么为什么会产生hash冲突呢？这也就是接下来要探讨的问题。

既是数组，必然会有长度，当我们在往数组中插入数据的时候，不管是什么类型的数据，对于数组来说，就是占据了某个下标对应的空间，那么当加入的数据越来越多的时候，是否会出现多个数据占据同一个位置呢？答案是肯定的，这就是hash冲突产生的原始因素；

首先，我们先弄清楚几个概念，对于hashMap或者其他类似的map来说，我们往里面添加数据的时候，并不是直接往数组里面加，而是通过计算这个插入数据的hash值，即通过一个hash的算法，然后把这个值加进去，以后再去查找数据的时候，hashMap同样会根据你的key，倒推出这个hash值然后取出数据，即这个hash值可以理解为插入值对应的数组下表；

但通过实验我们可以发现，hash函数计算不同的key的时候，可能得到相同的hash值，这样一来，如果再用这个hash值作为数组的标识这个值的下标，就无法定位这个值了，这个时候冲突就发生了；

下面我们用代码来模拟一下这个使用开发地址法解决hash冲突的问题，首先定义一个对象，这里为Info,为了更接近真实场景，我们这里的属性都为字符串，

什么是开放地址法呢？

\*\*

### 当冲突发生的时候，通过查找数组的一个空位，将数据插入进去，而不再用hash函数计算获取数的下标，这个方法就叫做开发地址法； ###

\*\*

public class Info {
    	private String key;			//关键字，或者能标识对象的唯一属性
    	private String name;		//值域
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    }

接下来手工写一个hashTable，用于模拟hashMap,

/**
     * 模拟hashMap
     *
     */
    public class HashTable {
    	
    	private Info[] arr;
    	
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new Info[100];
    	}
    	
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new Info[maxSize];
    	}
    	
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		//获得关键字
    		String key = info.getKey();
    		//关键字所自定的哈希数
    		int hashVal = hashCode(key);
    		//如果这个索引已经被占用，而且里面是一个未被删除的数据
    		while(arr[hashVal] != null && arr[hashVal].getName() != null) {
    			//进行递加，避免漏找
    			++hashVal;
    			//循环
    			hashVal %= arr.length;
    		}
    		arr[hashVal] = info;
    	}
    	
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		int hashVal = hashCode(key);
    		while(arr[hashVal] != null) {
    			if(arr[hashVal].getKey().equals(key)) {
    				return arr[hashVal];
    			}
    			++hashVal;
    			hashVal %= arr.length;
    		}
    		return null;
    	}
    	
    	/**
    	 * 删除数据
    	 */
    	public Info delete(String key) {
    		int hashVal = hashCode(key);
    		//循环查找，数组中下标为hashVal的值，没有找到返回null
    		while(arr[hashVal] != null) {
    			if(arr[hashVal].getKey().equals(key)) {
    				Info tmp = arr[hashVal];
    				tmp.setName(null);
    				return tmp;
    			}
    			++hashVal;			//由于数组的值是连续的，为了避免漏找，需要依次往下找
    			hashVal %= arr.length;
    		}
    		return null;
    	}
    	
    	/**
    	 * 获得关键字的hash值，也可以自定义
    	 */
    	public int hashCode(String key) {
    		
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for(int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    }

可以看到，我们是通过对要插入的数值先进行hash编码，再对数值的长度进行取模i，这样得到的位置总能够落在数值的长度内，

里面有个地方可能不太好理解，就是在插入数据的时候，我们使用while循环进行插入，既然是开发地址，也就是说数组的每一个闲置的空间我们都能使用，前提是这个位置没有被其他的值占用，由于数组是连续的，所以我们需要循环的去寻找一个这样的位置，所以才有 ++hashVal这段代码，直到找到了一个空位，然后我们把数据插入进去，

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]

运行测试main方法，我们看到，数据成功插入，但通过hash函数计算得到的“a”和"ct"却是一样的，再一次印证了我们前面所说的问题，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 2]

**以上便是所说的采用开发地址法解决hash冲突的解决方法，但这样就万无一失了吗？**

我们考虑一下，数据的长度是有限的，但我们可能会往数组里面添加很多数据进去，数组总有被填满的时候，那样开发地址法也不管用了，当然，实际业务中，如果可以预料数据的大小，我们可以采用这样的方式解决部分问题，但问题是这样确实不是万无一失的解决办法，

更合适的方式是什么呢？其实就是hashMap中使用较多的链地址法，也就是一开始我们图中展示的，基本结构仍然是一个数组，但是数组的每个单元维护的不再是一个个数据，而是一个个链表，也就是类似于linkedList这样的结构,当新插入的多个数据通过计算hash函数得到的是相同的数组下标时候，我们只需要把值往这个索引位置维护的链表中插入即可，什么是链地址法呢？

\*\*

### 在hash表每个单元中设置链表，某个要插入的数据项的关键字还是像通常那样映射到hash表的某个单元中，而数据项的本身则被插入到该单元维护的链表中； ###

\*\*

下面用代码来实现一下这个过程，同上面所有不同的是，链表中的结构我们通过是维护者一个个节点，即Node ，对链表结构不熟悉的同学可以先自行百度一下，不是很难，

1、定义一个对象Info,

public class Info {
    	
    	private String key;
    	private String name;
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    	
    	
    	
    }

2、定义一个Node作为链表中的基本存储单元，

public class Node {
    
    	// 数据域
    	public Info info;
    	// 指针域,指向对下一个节点引用
    	public Node next;
    
    	public Node(Info info) {
    		this.info = info;
    	}
    
    }

3、定义一个链表，

/**
     * 模拟linkedList
     * 
     * @author asus
     *
     */
    public class LinkList {
    
    	// 头结点
    	private Node first;
    
    	public LinkList() {
    		first = null;
    	}
    
    	// 插入一个节点
    	public void insertFirst(Info info) {
    		Node node = new Node(info);
    		node.next = first;
    		first = node;
    	}
    
    	// 删除一个节点，在头结点后进行删除
    	public Node deleteFirst() {
    		Node temp = first;
    		first = temp.next;
    		return temp;
    	}
    
    	/**
    	 * 查找方法
    	 */
    	public Node find(String key) {
    		Node current = first;
    		while (!key.equals(current.info.getKey())) {
    			if (current.next == null) {
    				return null;
    			}
    			current = current.next;
    		}
    		return current;
    	}
    
    	/**
    	 * 删除方法
    	 */
    	public Node delete(String key) {
    		Node current = first;
    		Node previous = first;
    		while (!key.equals(current.info.getKey())) {
    			if (current.next == null) {
    				return null;
    			}
    			previous = current;
    			current = current.next;
    		}
    
    		if (current == first) {
    			first = first.next;
    		} else {
    			previous.next = current.next;
    		}
    		return current;
    
    	}
    
    }

4、模拟hashMap的几个方法，

public class HashTable {
    
    	private LinkList[] arr;
    
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new LinkList[100];
    	}
    
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new LinkList[maxSize];
    	}
    
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		String key = info.getKey();
    		// 获取关键字的自定义hash函数
    		int hashVal = hashCode(key);
    
    		if (arr[hashVal] == null) {		//如果数组某个单元的位置为空，则需要重新构造一个linkList
    			arr[hashVal] = new LinkList();
    		}
    		arr[hashVal].insertFirst(info);
    	}
    
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		int hashVal = hashCode(key);
    		return arr[hashVal].find(key).info;
    	}
    	
    	/**
    	 * 删除数据
    	 */
    	public Info delete(String key){
    		int hashVal = hashCode(key);
    		return arr[hashVal].delete(key).info;
    	}
    	
    
    	/**
    	 * 自定义计算hash的函数
    	 */
    	public int hashCode(String key) {
    
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for (int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    
    }

和上面开发地址法插入数据和查找数据不同，此种方式进行数据查找的时候，其实是进行两次查到的，第一次定位数组中的位置，第二次去到链表中，调用链表的查找方法进行查找，这一点值得注意，插入和删除的思想也是类似，  
![在这里插入图片描述][20190127184514839.png]

下面我们来测试一下，可以看到，依然达到了效果，说明我们模拟的链地址法也生效了，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 3]

以上就是通过开发地址法和链地址法解决hash冲突的两种方式，希望对大家理解hashMap的底层原理有所帮助…感谢观看！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190127175517374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190127182221794.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190127182717695.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[20190127184514839.png]: https://img-blog.csdnimg.cn/20190127184514839.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190127184811431.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70