本文主要內(nèi)容
1章贞、List接口
2、Set接口
3非洲、棧鸭限、隊列、數(shù)組怪蔑、列表數(shù)據(jù)的存儲結(jié)構(gòu)
4里覆、哈希表的原理和存儲

01 List接口

A:List接口的特點
a:存取順序一致
b:有索引，通過索引可以精確的操作集合中的元素
c:可存儲重復(fù)元素
d:List接口的常用子類：ArrayList缆瓣、LinkedList

B:List接口特有方法
a:增加元素方法
add(Object e)：向集合末尾處喧枷，添加指定的元素
add(int index, Object e) 向集合指定索引處，添加指定的元素弓坞，原有元素依次后移

b:刪除元素刪除
remove(Object e)：將指定元素對象隧甚，從集合中刪除，返回值為被刪除的元素
remove(int index)：將指定索引處的元素渡冻，從集合中刪除戚扳，返回值為被刪除的元素

c:替換元素方法
E set(int index, Object E)：將指定索引處的元素，替換成指定的元素族吻，返回值為替換前的元素

d:查詢元素方法
get(int index)：獲取指定索引處的元素帽借，并返回該元素

C:迭代器的并發(fā)修改異常
迭代器的并發(fā)修改異常 java.util.ConcurrentModificationException
即在遍歷的過程中,使用了集合方法修改了集合的長度，致迭代器并不知道集合中的變化超歌，容易引發(fā)數(shù)據(jù)的不確定性砍艾。

D:ArrayList集合
ArrayList集合特點:底層采用的是數(shù)組結(jié)構(gòu)

 ArrayList al=new ArrayList();//創(chuàng)建了一個長度為0的Object類型數(shù)組
 al.add("abc");//底層會創(chuàng)建一個長度為10的Object數(shù)組 Object[] obj=new Object[10]
               //obj[0]="abc"
              //如果添加的元素的超過10個,底層會開辟一個1.5*10的長度的新數(shù)組
              //把原數(shù)組中的元素拷貝到新數(shù)組,再把最后一個元素添加到新數(shù)組中
 原數(shù)組:
 a b c d e f g h k l
 添加m:
 a b c d e f g h k l m null null null null

E:LinkedList集合
a、LinkedList集合特點
底層采用鏈表結(jié)構(gòu),每次查詢都要從鏈頭或鏈尾找起,查詢相對數(shù)組較慢
LinkedList的索引決定是從鏈頭開始找還是從鏈尾開始找巍举。如果該元素小于元素長度一半,從鏈頭開始找起,如果大于元素長度的一半,則從鏈尾找起

b脆荷、LinkedList特有方法
E removeFirst() 移除并返回鏈表的開頭
E removeLast() 移除并返回鏈表的結(jié)尾
E getFirst() 獲取鏈表的開頭
E getLast() 獲取鏈表的結(jié)尾
addFirst(E) 添加到鏈表的開頭
addLast(E) 添加到鏈表的結(jié)尾

F:Vector類的特點
Vector集合數(shù)據(jù)存儲的結(jié)構(gòu)是數(shù)組結(jié)構(gòu)，為JDK中最早提供的集合,是線程同步的
Vector中提供了一個獨特的取出方式:枚舉Enumeration，它是早期的迭代器(與 Iterator 接口的功能是類似的)蜓谋。
Vector集合已被ArrayList替代梦皮。枚舉Enumeration已被迭代器Iterator替代。

02 Set接口

A:Set接口的特點
a:不包含重復(fù)元素,無索引
b:Set集合取出元素的方式可以采用：迭代器桃焕、增強for剑肯。
c:Set集合有多個子類，常用的有HashSet覆旭、LinkedHashSet退子。
d:Set接口的實現(xiàn)類,HashSet (哈希表):無序集合,存儲和取出的順序不同,沒有索引,不存儲重復(fù)元素

B:LinkedHashSet集合特點
inkedHashSet 基于鏈表的哈希表實現(xiàn)，繼承自HashSet
LinkedHashSet 自身特性,具有順序,存儲和取出的順序相同的
線程不安全的集合,運行速度塊

C:ArrayList,HashSet判斷對象是否重復(fù)的原因

a:ArrayList的contains方法原理:底層依賴于equals方法
ArrayList的contains方法會使用調(diào)用方法時型将，
傳入的元素的equals方法依次與集合中的舊元素所比較，
從而根據(jù)返回的布爾值判斷是否有重復(fù)元素荐虐。
此時七兜，當(dāng)ArrayList存放自定義類型時，由于自定義類型在未重寫equals方法前福扬，
判斷是否重復(fù)的依據(jù)是地址值腕铸，所以如果想根據(jù)內(nèi)容判斷是否為重復(fù)元素，需要重寫元素的equals方法铛碑。

b:HashSet的add()方法和contains方法()底層都依賴 hashCode()方法與equals方法()
Set集合不能存放重復(fù)元素狠裹，其添加方法在添加時會判斷是否有重復(fù)元素，有重復(fù)不添加汽烦，沒重復(fù)則添加涛菠。
HashSet集合由于是無序的，其判斷唯一的依據(jù)是元素類型的hashCode與equals方法的返回結(jié)果撇吞。規(guī)則如下：
先判斷新元素與集合內(nèi)已經(jīng)有的舊元素的HashCode值
如果不同俗冻，說明是不同元素，添加到集合牍颈。
如果相同迄薄，再判斷equals比較結(jié)果。返回true則相同元素煮岁；返回false則不同元素讥蔽，添加到集合。

所以画机，使用HashSet存儲自定義類型冶伞，如果沒有重寫該類的hashCode與equals方法，則判斷重復(fù)時色罚，使用的是地址值碰缔，如果想通過內(nèi)容比較元素是否相同，需要重寫該元素類的hashcode與equals方法戳护。

03棧金抡、隊列瀑焦、數(shù)組、列表數(shù)據(jù)的存儲結(jié)構(gòu)

a:棧結(jié)構(gòu):后進先出/先進后出(手槍彈夾)
b:隊列結(jié)構(gòu):先進先出/后進后出(銀行排隊)
c:數(shù)組結(jié)構(gòu):
查詢快:通過索引快速找到元素
增刪慢:每次增刪都需要開辟新的數(shù)組,將老數(shù)組中的元素拷貝到新數(shù)組中
開辟新數(shù)組耗費資源
d:鏈表結(jié)構(gòu)
查詢慢:每次都需要從鏈頭或者鏈尾找起
增刪快:只需要修改元素記錄的下個元素的地址值即可不需要移動大量元素

04 哈希表的存儲

A:哈希表的數(shù)據(jù)結(jié)構(gòu)
加載因子:表中填入的記錄數(shù)/哈希表的長度
例如:
加載因子是0.75 代表:
數(shù)組中的16個位置,其中存入160.75=12個元素
如果在存入第十三個(>12)元素,導(dǎo)致存儲鏈子過長,會降低哈希表的性能,那么此時會擴充哈希表(在哈希),底層會開辟一個長度為原長度2倍的數(shù)組,把老元素拷貝到新數(shù)組中,再把新元素添加數(shù)組中
當(dāng)存入元素數(shù)量>哈希表長度加載因子,就要擴容,因此加載因子決定擴容時機

B:字符串對象重寫重寫hashCode()方法
字符串對象的哈希值為普通的十進制整數(shù)
重寫父類Object的方法：public int hashCode()

  public class HashDemo {
    public static void main(String[] args) {
      Person p = new Person();
      int i = p.hashCode();
      System.out.println(i);
    
      String s1 = new String("abc");
      String s2 = new String("abc");
      System.out.println(s1.hashCode());
      System.out.println(s2.hashCode());
      
      /*System.out.println("重地".hashCode());
      System.out.println("通話".hashCode());*/
    }
  }
 
  //String類重寫hashCode()方法
  //字符串都會存儲在底層的value數(shù)組中{'a','b','c'}
  public int hashCode() {
          int h = hash;//hash初值為0
          if (h == 0 && value.length > 0) {
              char val[] = value;

              for (int i = 0; i < value.length; i++) {
                  h = 31 * h + val[i];
              }
              hash = h;
          }
          return h;
      }

C:哈希表的存儲過程
1.首先調(diào)用本類的hashCode()方法算出哈希值
2.在容器中找是否與新元素哈希值相同的老元素,
如果沒有直接存入
如果有轉(zhuǎn)到第三步
3.新元素會與該索引位置下的老元素利用equals方法一一對比
一旦新元素.equals(老元素)返回true,停止對比,說明重復(fù),不再存入
如果與該索引位置下的老元素都通過equals方法對比返回false,說明沒有重復(fù),存入

D:哈希表的存儲自定義對象
HashSet集合的自身特點:
底層數(shù)據(jù)結(jié)構(gòu),哈希表
存儲,取出都比較快
線程不安全,運行速度快

E:自定義對象重寫hashCode和equals

     public class HashSetDemo1 {
      public static void main(String[] args) {
        
        //將Person對象中的姓名,年齡,相同數(shù)據(jù),看作同一個對象
        //判斷對象是否重復(fù),依賴對象自己的方法 hashCode,equals
        HashSet<Person> setPerson = new HashSet<Person>();
        setPerson.add(new Person("a",11));
        setPerson.add(new Person("b",10));
        setPerson.add(new Person("b",10));
        setPerson.add(new Person("c",25));
        setPerson.add(new Person("d",19));
        setPerson.add(new Person("e",17));
        System.out.println(setPerson);
      }
     }
    
    public class Person {
      private String name;
      private int age;

      /*
       *  沒有做重寫父類,每次運行結(jié)果都是不同整數(shù)
       *  如果子類重寫父類的方法,哈希值,自定義的
       *  存儲到HashSet集合的依據(jù)
       *   
       *  盡可能讓不同的屬性值產(chǎn)生不同的哈希值,這樣就不用再調(diào)用equals方法去比較屬性
       *
       */
      public int hashCode(){
        return name.hashCode()+age*55;
      }
      //方法equals重寫父類,保證和父類相同
      //public boolean equals(Object obj){}
      public boolean equals(Object obj){
        if(this == obj)
          return true;
        if(obj == null)
          return false;
        if(obj instanceof Person){
          Person p = (Person)obj;
          return name.equals(p.name) && age==p.age;
        }
        return false;
      }
      
      public String getName() {
        return name;
      }
      public void setName(String name) {
        this.name = name;
      }
      public int getAge() {
        return age;
      }
      public void setAge(int age) {
        this.age = age;
      }
      public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
      }
      public Person(){}
      
      public String toString(){
        return name+".."+age;
      }
     }

F:hashCode和equals方法的面試題
兩個對象 Person p1 p2

問題: 如果兩個對象的哈希值相同 p1.hashCode()==p2.hashCode()梗肝，兩個對象的equals一定返回true嗎 p1.equals(p2) 一定是true嗎
正確答案:不一定

如果兩個對象的equals方法返回true,p1.equals(p2)==true榛瓮，兩個對象的哈希值一定相同嗎
正確答案: 一定

在 Java 應(yīng)用程序執(zhí)行期間
1.如果根據(jù) equals(Object) 方法，兩個對象是相等的巫击，那么對這兩個對象中的每個對象調(diào)用 hashCode 方法都必須生成相同的整數(shù)結(jié)果禀晓。
2.如果根據(jù) equals(java.lang.Object) 方法，兩個對象不相等坝锰，那么對這兩個對象中的任一對象上調(diào)用 hashCode 方法不 要求一定生成不同的整數(shù)結(jié)果粹懒。
兩個對象不同(對象屬性值不同) equals返回false=====>兩個對象調(diào)用hashCode()方法哈希值相同
兩個對象調(diào)用hashCode()方法哈希值不同=====>equals返回true
兩個對象不同(對象屬性值不同) equals返回false=====>兩個對象調(diào)用hashCode()方法哈希值不同
兩個對象調(diào)用hashCode()方法哈希值相同=====>equals返回true
所以說兩個對象哈希值無論相同還是不同,equals都可能返回true