跟面试官扯！HashMap集合

向右看齐 2023-10-07 12:22 12阅读 0赞

HashMap底层源码:

主干的初始化长度为16(以后扩展必须是2的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    负载因子，代表了table的填充度有多少，默认是0.75
    加载因子存在的原因，还是因为减缓哈希冲突，因为初始桶数组的长度为16，
    等到满16个元素在扩容，某些桶里可能就有不止一个元素了。(因为单向链)
    所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    HashMap的桶数组，可以看到就是一个Entry数组，初始值为空数组{
        }，桶数组的长度一定是2的次幂。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

### 首先我们创建了！源码的桶数组 默认长度16 ###

四维图的第二步！！！！

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

### 添加数据以后，生成的hash值！！！对后面的修改 单向链做基础 ###

四维图第三步:

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

### 获取到生成的hash值 进行判断，为空(就是新的hash值) 就直接添加数据成功！！(纵向添加成功) ###

四维图4，5步:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 2]

### 如果hash值不为空！跟前面添加的数据hash值相同时 则横向添加：俗称单向挂链 ###

而且这儿的挂链超过8的时候，就开始红黑树的计算！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 4]  
hash值相同时候，开始单向挂链！  
![在这里插入图片描述][20200409145833396.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 6]  
结合上图看运行结果 ！！

10对象数字产生的数字格式
    4对象数字产生的数字格式
    14对象数字产生的数字格式
    8对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    12对象数字产生的数字格式
    [20,bb, 21,dd, 37,jj, 53,dd, 69,ee, 85,ff, 40,dd, 10,aa, 60,oo, 30,cc] 
    次数10

在hash值相同的时候，在hash值为5的 put数据69里面开始寻找  
也就是找相同的key值！！！  
被找到的hash值就会被 新的数据覆盖！！！  
![在这里插入图片描述][202004091509540.png]  
![在这里插入图片描述][20200409150832765.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 7]

### 源码在最后的: 最终源码 ###

思维图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 8]

测试前的源码:

package com.xiaoluo.demo;
    
    public class text {
        
    	public static void main(String[] args) {
        
    		Maptest mp=new Maptest();
    		mp.put(10, "aa");
    		mp.put(20, "bb");
    		mp.put(30, "cc");
    		mp.put(40, "dd");
    		mp.put(50, "ee");
    		mp.put(60, "ff");
    
    	}
    
    }

测试数据长度，展示添加，修改等方法  
最终源码:

newNode.hash=this.myHash(key.hashCode(), table.length); // 产生0-15之间的数  
System.out.println(newNode.hash+“对象数字产生的数字格式”);

### 通过键值获取对应的值！！简单的删除remove方法代码如下 ###

删除有点小BUG 但是不影响  
获取单向链值的时候，获取的是最后覆盖后的值(横向添加链)

/***
    	 * 通过键获取对应的值
    	 * 
    	 */
    	public Object get(Object key){
        
    		//求key的hash值
    		int hash=this.myHash(key.hashCode(), table.length);
    		Object value=null;
    		
    		if (table[hash]!=null) {
        //获取横向hash值
    			Node temp=table[hash];   //找到第一个hash节点
    			while (temp!=null) {
            //横向如果还有节点      ，也就是单向链进行遍历
    				if (temp.key.equals(key)) {
        
    					value=temp.value;
    					break;					
    				}
    				else{
        
    					temp=temp.next;  //求下一个横向节点，寻找单向链后面的值
    				}	
    			}	
    		}
    		return value;   //把值返回
    	}
    	public void remove(Object key){
        
    		int hash=this.myHash(key.hashCode(), table.length);	
    		if (table[hash]!=null) {
        
    			Node temp=table[hash];   //找到第一个节点
    			while (temp!=null) {
            //横向如果还有节点进行遍历
    				if (temp.key.equals(key)) {
        
    					temp.value=null;
    					break;					
    				}
    				else{
        
    					temp=temp.next;  //求下一个横向节点
    				}	
    			}	
    		}
    		
    	}

你看下面69的键值！！！！被覆盖！

package com.xiaoluo.demo;
    
    public class text {
        
    	public static void main(String[] args) {
        
    		Maptest mt=new Maptest();
    		mt.put(10, "aa");
    		mt.put(20, "bb");
    		mt.put(30, "cc");
    		mt.put(40, "dd");
    		mt.put(21, "dd");
    		mt.put(37, "jj");
    		mt.put(53, "dd");
    		mt.put(69, "ee");
    		mt.put(69, "喜欢吃汤圆");
    		mt.put(85, "ff");
    		list.remove(85);
    		System.out.println(mt);
    		
    		System.out.println("次数"+mt.size);
    		System.out.println(mt.get(30));
    		System.out.println(mt.get(69));
    		
    		
    		
    	} 
    
    }
    运行结果:
    10对象数字产生的数字格式
    4对象数字产生的数字格式
    14对象数字产生的数字格式
    8对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    5对象数字产生的数字格式
    [20,bb, 21,dd, 37,jj, 53,dd, 69,喜欢吃汤圆, 85,ff, 40,dd, 10,aa, 30,cc] 
    次数9
    cc
    喜欢吃汤圆
    [20,bb, 21,dd, 37,jj, 53,dd, 69,喜欢吃汤圆, 85,null, 40,dd, 10,aa, 30,cc]   //有点问题！没有删除干净

完整源码:

package com.xiaoluo.demo;
    /***
     * HashMap底层原理
     * @author 戴尔
     *
     */
    public class Maptest {
        
    
    	static class Node{
        
    		int hash;
    		Object key;
    		Object value;
    		Node next;
    
    	}
    	//HashMap集合的属性
    	Node[] table;  //创建一个Node结合
    	int size;      //有效位数
    	int modelCount;  //计数器
    	
    	public  Maptest(){
        
    		table=new Node[16];   //默认大小是16
    		
    	}
    	
    	/***
    	 * 添加的方法
    	 * @param key   键 
    	 * @param value 值
    	 */
    	public void put(Object key,Object value){
        
    		Node newNode=new Node();
    		//给Node里面的每个属性赋值
    		//key.hashCode()----表示的是对象数字的格式
    		newNode.hash=this.myHash(key.hashCode(), table.length);    //	    产生0-15之间的数
    	System.out.println(newNode.hash+"对象数字产生的数字格式");
    //		System.out.println(key.hashCode());
    		newNode.key=key;
    		newNode.value=value;
    		newNode.next=null;  //第一次添加的时候没有拉链的过程，第二次可能有		
    		Node lastNode=null;
    		boolean flag=false;   //判断	
    		Node temp=table[newNode.hash]; //把某个节点hash获得到了
    		if (temp==null) {
        
    			//纵向添加 
    			table[newNode.hash] =newNode;	
    			modelCount++;
    		}
    		else{
        //修改----hash值一致  key一致完成修改的操作，(value)
    			//添加 -----找到最后一个节点，把最后的一个节点和添加的节点挂链(单链)
    			//外层循环控制的是行数      内层节点控制的是横向挂链
    			while (temp!=null) {
        
    				if (temp.key.equals(key)) {
        //修改
    					flag=true;
    					temp.value=value;
    					break;
    					
    				}
    				else{
        //key不重复的情况下
    					//也是一个添加,挂链的添加
    					lastNode=temp;   //拿到了横向节点的最后一个节点	
    					temp=temp.next; //下一个节点		
    					//不能保证一直添加，要找到最后一个添加找到next，才在下面if判断里进行拉链添加
    				}			
    			}
    			if (!flag) {
        
    				//拉链的添加
    				lastNode.next=newNode;
    				modelCount++;		
    			}			
    		}
    		size=modelCount;
    	}
    	
    	
    	/***
    	 * 通过键获取对应的值
    	 * 
    	 */
    	public Object get(Object key){
        
    		//求key的hash值
    		int hash=this.myHash(key.hashCode(), table.length);
    		Object value=null;
    		
    		if (table[hash]!=null) {
        //获取横向hash值
    			Node temp=table[hash];   //找到第一个hash节点
    			while (temp!=null) {
            //横向如果还有节点      ，也就是单链进行遍历
    				if (temp.key.equals(key)) {
        
    					value=temp.value;
    					break;					
    				}
    				else{
        
    					temp=temp.next;  //求下一个横向节点，寻找单向链后面的值
    				}	
    			}	
    		}
    		return value;   //把值返回
    	}
    	public void remove(Object key){
        
    		int hash=this.myHash(key.hashCode(), table.length);	
    		if (table[hash]!=null) {
        
    			Node temp=table[hash];   //找到第一个节点
    			while (temp!=null) {
            //横向如果还有节点进行遍历
    				if (temp.key.equals(key)) {
        
    					temp.value=null;
    					break;					
    				}
    				else{
        
    					temp=temp.next;  //求下一个横向节点
    				}	
    			}	
    		}
    		
    	}
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	/***
    	 * 显示方法
    	 */
    	public String toString(){
        
    		StringBuilder sb=new StringBuilder();
    		sb.append("[");
    		for (int i = 0; i < table.length; i++) {
        
    			//横着遍历  拿到当前的节点
    			Node temp=table[i];  //拿到某一列的第一个节点
    			while(temp!=null){
        
    				sb.append(temp.key +","+temp.value+ ", ");//[10:aa,20:bb,
    				temp=temp.next;
    				
    			}	
    		}
    		sb.setCharAt(sb.length()-2, ']');
    		return sb.toString();
    		
    	}
    	
    	public int myHash(int v,int length){
        
    //		return v % length -1;    //这里面只能算出0-14之间的数组
    		return v & length -1;    //这里面只能算出0-15之间的数组
    	}
    	
    
    }

[美团技术团队的图片][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200409113520361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200409145118282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020040914532138.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200409145533250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200409145625432.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[20200409145833396.png]: https://img-blog.csdnimg.cn/20200409145833396.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020040914284378.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200409142933985.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[202004091509540.png]: https://img-blog.csdnimg.cn/202004091509540.png
[20200409150832765.png]: https://img-blog.csdnimg.cn/20200409150832765.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200409150251449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200409143639195.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70
[Link 1]: https://tech.meituan.com/2016/06/24/java-hashmap.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200409172833362.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NxTDUyMGxU,size_16,color_FFFFFF,t_70