[数据结构与算法]什么是Hashmap及集合全家桶

前言

hashmap作为面试重点下面让我们进行了解
在学Hashmap前我们先来复习一下什么是集合

一、什么是集合？

集合：长度可以动态的增减，可以存放不同类型的元素，java中，所有的集合都放在Java.util包下
Collection 体系:

	Collection (接口)  ==> List  接口  ==> ArrayList
																		 ==> LinkedList
																		 ==> Vector ==>Stack (类)
																		        
			
										 ==> Set 接口 ==> HashSet
										 							==> TreeSet
										 							
										 ==> Queue  接口

List和set的区别（干货）
list有序 按照对象计入的顺序保存，可重复，允许多个null对象，可以使用iterrater取出元素 也可以用get方法.
set无序，不可重复，最多允许一个null元素对象，取元素只能用iterater.

二、重写equals ，hash，自定义compare

1.ArrayList重写equals

equals比较是堆中内存对象的地址

List集合,进行元素相等比较的时候用的是 元素的 equals 方法，如果在List集合中存放自定义对象,最好重写自定义对象的 equals() 方法

代码如下（示例）：

//比较对象定位Cat   List list=new ArrayList();
       //  list.add(new Cat(1,"tom","中国","黑"));
public boolean equals(Object obj){
           if(this==obj)
           return true;
           if(!(obj instanceof Cat)){
           return fasle;
           Cat cat = (Cat) obj;
           if(this.name.equals(cat.name) && this.age==cat.age && this.address.equals(cat.address) &&this.color.equals(cat.color)) {
						return true;	
					}
					else {
						return false;
					}
}

2.HashSet重写equals和hashCode

以前我们学的List集合,进行相等比较的时候,用的是元素的 equals()方法
HashSet集合,进行相等比较的时候, 它是先比较元素的 hashCode() 方法的返回值。如果返回值相同,再调用equals() 进行比较

代码如下（示例）：

 //重写hashCode()    Set set=new HashSet();
					//set .add(new Cat(2,"tom"));
				public int hashCode() {
					/*
					int result=17;
					result=31*result+name.hashCode();
					result=31*result+age;
					return result;  */
					//因为 31* i可以被jvm优化成 i<<5-i
					
					return Objects.hash(age,name);	
				}
//重写equals
                public boolean equals(Object o) {
					if(this==o) 
						return true;
					if(!(o instanceof Cat))
						return false;
					
					Cat c=(Cat)o;
			    if(this.age==c.age&&this.name.equals(c.name)) 
						return true;
					
					return false;
				}	

3.TreeSet自定义类型进行排序

//例子 使用匿名内部类
、/*TreeSet t=new TreeSet(new StrLenComp() ) ;
					t.add("this");
					t.add("aog");
					t.add("vvvvv");
					t.add("buffer");
					t.add("ship");
					t.add("longlong");
					t.add("wha");
					t.add("ha");*/
			   	TreeSet t=new TreeSet(new Comparator() {
							public int compare(Object o1, Object o2) {
								String s1=(String)o1;
								String s2=(String)o2;
								
								if(s1.length()>s2.length()) {
									return 1;
								}
								else {
									return -1;
								}
							}
							
						} ) ;

什么是HashMap

众所周知，HashMap是一个用于存储Key-Value键值对的集合，每个简直对也叫做Entry。这些个简直对（entry）分散存储在一个数组当中，这个数组就是HashMap的主干。
HashMap数组每个元素的初始值都是Null.

1.put方法的原理

调用Put方法的时候发生了什么呢？
比如调用hashMap.put(“luanma”,0),插入一个Key为“luanma” 的元素，这是我们需要利用一个哈希函数来确定Entry的插入位置（index）.
注意：HashMap数组每个元素不止是一个Entry对象，当映射到冲突的数组位置时，运用链表头插法，代替原来的Entry之前的变成当前Entry的下一个节点

2.get方法原理

把输入的Key做一次Hash映射，index = Hash（“luanma”）得到对应的index：比配Key值，返回Value。HashMap的发明者认为，后插入的Entry被查找的可能性更大。1.7为头插发，1.8为尾插法

3.HashMap的相关说明

    1) 默认初始容量
		    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16 , 必须是2的整数次方(以后扩容的时候也是这样)
		    
		2) 最大容量
		    static final int MAXIMUM_CAPACITY = 1 << 30; 
		    
		3) 默认装载因子
		    static final float DEFAULT_LOAD_FACTOR = 0.75f   //值可以大于1 
		        这个值越小,操作的速度越快(是因为产生hash冲突的可能性降低了,省去很多链表操作),但浪费空间
		        这个值大,效果和上面相同 , 速度会慢 (装的满,产生hash 冲突的可能性就高), 但节省空间
		        
		4) static final int TREEIFY_THRESHOLD = 8; //链表变成红黑树的临界值,链表的长度到达这个值以后,就成红黑树 
		
		5) static final int UNTREEIFY_THRESHOLD = 6;  //当数据从红黑树中移除,数据减小到这个值的时候,还原成链表
		
		6) static final int MIN_TREEIFY_CAPACITY = 64; //当链表转成红黑树之前,还要进行一次判断,看看map集合中的数据总量是不是到达这个值了,到了才转换,不到不转换
		                                               // 防止在哈希表建立初期,多个键正好放到了一个节点上的情况
		                                               7) transient int size; //装的键值对的个数
  
        8) transient Node<K,V>[] table;  //哈希桶
  
        9) final float loadFactor; //用户指定的装载因子
  
        10) int threshold; // hashMap 进行扩容临界值

重要方法
1) 哈希函数 ,又叫扰动函数 ,也叫散列值优化函数 ,它的目的是降底 hash值 冲突的可能性

	    static final int hash(Object key) {
	    		int h;
	    		if(key == null){
	    				return 0;
	    		}
	    		else{
	    		 	h = key.hashCode()
	    		 	h = h^(h >>> 16);   //移位以后,进行异或,会让原来的数的高,低位都参与运算,让结果更混乱
	    		}
	    		
	    		return h;		
	    }
	     2) 根据哈希值, 计算元素在哈希桶中的索引  
	     //h 哈希值
	     //length 是哈希桶的长度,它总是2的n次方
	     public int indexFor(int h, int length){
	     		return h&(length-1);   //这个写法,相当于 h % length 求余   (前题,是length 必须是2的整数次方)