从Java集合类开始：

HashMap
HashTable
ConcurrentHashMap
HashSet
LinkedHashSet
String

image.png

一、HashMap： https://www.cnblogs.com/ITtangtang/p/3948406.html）

1、数据结构：底层（数组+链表）
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable,Serializable
继承了map接口，clonable接口(有clone()方法)，serializable（可序列化）

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。HashMap底层是通过链表来解决hash冲突的。

**碰撞/产生哈希冲突：是指两者的key计算的index相同==>解决哈希冲突的方式：通过增加链表解决哈希冲突。
查询：指的是已经找到数组的某个位置，遍历某个位置上的链表的过程。 **

2、具体源码：

（1）首先，在HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，hashcode，Entry类实则是单向链表，其对象中包含了键和值，其中next也是一个Entry对象。
整个table是一个数组，是Entry数组，每一个数组位就是代表该位置的第一个Entry，它又会一直往后链接成该位置的一条链表，table = new Entry[capacity]；如table[0]指的是存在table位置的那条链表的头结点，它又会链接到往后的Entry结点，形成一条链表。

（2）关键属性：

 transient Entry[] table;//存储元素的实体数组
 transient int size;//存放元素的个数
 int threshold; //临界值   当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量
 final float loadFactor; //加载因子
 transient int modCount;//被修改的次数

默认初始容量为16，默认负载因子为0.75。而160.75=12这是实际大小的临界值，超过这个临界值，会进行扩容。
哈希表的容量为2的n次方，扩容为初始容量负载因子。

加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）。

冲突的机会越大,则查找的成本越高。

若机器内存足够，要提高查询速度，则将加载因子取小；如果机器内存紧张，且对查询速度无要求则可以将加载因子设大；一般默认0.75。

HashMap解决哈希冲突的方式是：链地址法
即先通过hash()找到数组中的位置，再通过equals和==找到这个位置其后的链表中相同的key，无则直接put，有则新值取代旧值，返回旧值。

（3）方法：
求哈希值：key.hashCode()
比较值：key.equals(k)
都是Object类的方法

当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；
当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

(a)构造方法：
如果指定了初始容量和负载因子，则构造函数中要确保容量为2的n次幂，使真正的初始容量位capacity为大于initialCapacity的最小的2的n次幂。
···
public HashMap(int initCapacity, float loadFactor）{
....
int capacity = 1; //初始容量
while (capacity < initialCapacity) //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂
capacity <<= 1;
...
}
public HashMap(int initCapacity) //构造一个初始容量capacity为大于 initialCapacity的最小的2的n次幂，负载因子为0.75的hashmap
public HashMap() //构造一个初始容量为16，负载因子为0.75的hashmap
···

(b) put方法：完全不考虑value，只考虑key
1、已知key和value，求该key的hash值（int h=hash(key.hashCode()）===>决定存储位置。
2、根据hash值h在数组中找位置，indexFor()方法 (int index=h&(length-1)）
3、根据数组中的位置，用equals() 去链表中找有没有key相等的，有，则新值value覆盖旧值，并返回旧值，但Key不会覆盖，key相等；
4、如果在链表中找不到key相等的，返回false，新添加的Entry与原来的Entry形成Entry链，新添加的Entry位于Entry链的头部。
（取代的条件：两者hash值相等，所以数组中的位置等==>去链表中找，两者的key也相等(equals加==) if(e.hash==hash && ((k==e.key)==key) || key.equals(k))）

key为null，hash值为0，存在table[0]中

public V put(K key,V value){
//key为null，将该键值对添加到table[0]
 if (key == null)  return putForNullKey(value);
//key不为null，计算该key的哈希值，将其添加到该哈希值对应的链表中
int hash=hash(key.hashCode());
//搜索指定hash值在对应table中的索引
         int i = indexFor(hash, table.length);
//循环遍历Entry数组(即该key对应的链表)，如果该key对应键值对已存在，新value取代旧value，返回旧值
 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
 Object k;
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //这里的equals方法是Object类的
                  V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
              }
         }
//将key-value添加到table[i]处
     addEntry(hash, key, value, i);
}

(c) hashCode()：HashMap重写了Object的hash()，通过key的hashCode值计算hash码
为什么要重写？【增加hashcode的随机性,使散列分布更均匀】
让低16位同时包含了高位和低位的信息，在计算下标时，由于高位和低位的同时参与，减少hash的碰撞。之所以用异或而不用&，|：异或能更好的保留各部分的特征，&结果靠1，|结果靠0
key.hashCode()的作用是返回键值key所属类型自带的hashcode。
key为null，哈希值为0；key不为null，哈希值是key本身的哈希值异或它的高16位。

static final int hash(Object key){
      int h;
     return (key==null)?0:(h=key.hashCode())^(h>>>16);
     //key为null，哈希值为0；key不为null，哈希值是key本身的哈希值异或它的高16位(无符号右移16位，高位补0，则一般最后前16位是1)

image.png

解析！

(d)indexFor()：返回的类型是int。如果直接拿散列值作为下标访问HashMap的主数组的话，考虑到int类型值的范围[-2^31 , 2^31 -1]，虽然只要hash表映射比较松散的话，碰撞几率很小，但是直接做下标，映射空间太大，内存放不下，所以先做对数组的长度取模运算，得到的余数才能用来访问数组下标。

static int indexFor(int h,int length){
     return h&(length-1);   //可以确保算出的索引是在数组大小范围内，不会超出。
}

注意！！！
一般对哈希表的散列，是用hash值对length取模（除法散列法）——hashtable
但取模用到除法，效率低，hashmap是h&(length-1)，实现均匀散列，提高效率。是hashmap对hashtable的改进。

用多项式的公式计算，可以得到当length=2^n时，h%lenth=h&(length-1)

====>为什么哈希表的容量一定要是2的整数次幂呢？
（1）容量为2的n次幂，则h&(length-1)相当于对length取模，保证了散列的均匀，也提升了效率；
（2）length为2的整数次幂，则length-1为奇数，所以h&(length-1)的最后一位可能为0或1（取决于h），即结果可能为奇数/偶数，保证了三列的均匀性。（但如果length为奇数，则length-1为偶数，最后一位为0，h&(length-1)最后一位为0，只为偶数，所以任何hash值都会被散列到数组的偶数下标位置，就浪费了近一半的空间，增加了碰撞机率，减慢了查询机率。
所以，这能使不同hahs值发生碰撞的概率较小，使元素在哈希表中均匀散列。

(e)addEntry()：用于增加新结点，用hash，key，value构造一个新的Entry对象，放到所以bucketIndex的位置，把该位置原先对象设置为新对象的next，构成链表。
大于临界值就扩容，原来的table长度2扩容，（则此时临界值也会变化为新的长度负载因子）

void addEntry(int hash, K key, V value, int bucketIndex) {
         Entry<K,V> e = table[bucketIndex]; //如果要加入的位置有值，将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
         table[bucketIndex] = new Entry<>(hash, key, value, e);
         if (size++ >= threshold) //如果大于临界值就扩容
             resize(2 * table.length); //以2的倍数扩容
 }

（f)扩容/调整hashmap的大小：resize()
newCapacity是调整后的单位，调整为原来的2倍

void resize(int newCapacity) {
         Entry[] oldTable = table;
         int oldCapacity = oldTable.length;
         if (oldCapacity == MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE;
             return;
        }
 
        Entry[] newTable = new Entry[newCapacity];  //创建新的Entry[]
        transfer(newTable);//用来将原先table的元素全部移到newTable里面
        table = newTable;  //再将newTable赋值给table
        threshold = (int)(newCapacity * loadFactor);//重新计算临界值
    }

在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

当HashMap中元素个数超过临界值（=数组大小负载因子）时，扩容。
默认情况，数组大小16，当hashMap中元素个数超过160.75=12时，扩容，把数组大小扩展为2*16=32，扩大一倍，再重新计算每个元素在数组中的位置。

（g）get方法：数据读取
···
public V get(Object key){
if(key==null) return getForNullKey(); //key为null，
//求该key的哈希值
int hash=hash(key.hashCode())
//并用indexFor()查找table数组中对应位置，然后通过key的equals方法在链表中找到需要的元素。
for(Entry<K,V> e=table[indexFor(hash,table.length)]; e!=null; e=e.next){
Object k;
if(e.hash==hash&& ((k=e.key) ==key || key.equals(k))) //用equals方法找到相等的key的Entry，返回其value
return e.value;
}
return null； //查找不到，则返回Null
···

（h）HashMap自己的equals方法需要重写，逐一判断两个的哈希值，数组位置和链表中的位置。

（i）remove()：
在remove(key）根据removeEntryKey(key）方法返回的结果e是否为Null返回null或e.value.

public V remove(Object key) {
         Entry<K,V> e = removeEntryForKey(key);
         return (e == null ? null : e.value)；
   }

removeEntryKey(key)：删除单个节点，返回被移除的元素，不存在则返回null.
主要的实现：找到table数组中的位置，然后就是链表删除，修改指针，使要删除的节点的前一节点的next指向被删除节点的next。

（j）clear()：
清空，直接将table数组内容遍历设置为null，size=0

二、HashTable：效率低，方法都是synchronized，继承Directory类，线程安全。不允许key或value为null。在并发环境下，所有访问HashTable的线程都必须竞争同一把锁。
其中的方法和HashMap差不多，就是都是synchronized，线程安全的。

三、ConcurrentHashMap：是线程安全且高效的HashMap，锁分段技术。继承AbstractMap
容器里有多把锁，每把锁用于锁容器其中一部分的数据，当多线程访问容器里不同数据段的数据时，线程间不会存在锁竞争，可以有效提高并发访问效率。

先把数据分成一段一段地存储，再给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段地数据也能被其他线程访问。

image.png

由segment数组和hashEntry数组组成。
Segment对象是一种可重入锁，HashEntry对象是存储键值对数据。
一个ConcurrentHashMap包含一个数组Segment[]，每个segment和hashmap差不多，数组加链表，一个segment中包含一个entry[]数组，即它链接到entry[]中某个，而Entry是一种链表结构。
要对Entry数组进行修改，要先获得segment的锁。

1、每个segment的定义：

static final class Segment<K,V>  extends ReentrantLock implements Serializable

Segment继承了ReentrantLock(可重入锁)，表明每个segment都可以当作一个锁，因此对每个segment中的数据需要同步操作都是使用每个segment容器对象自身的锁来实现，只有对全局需要改变时锁定所有segment。分离锁。

2、ConcurrentHashmap初始化：
（a)初始化segments数组：
concurrencyLevel：初始化时一般会先给concurrencyLevel，其最大值65535，则segment数组最大长度65536
ssize：segment数组长度，是大于等于concurrencyLevel的最小的2的n次幂
sshift：是计算ssize时，扩大的n的值
segmentShift：段偏移量，定位参与散列运算的位数， =32- sshift （32是因为其hash()最大输出32位）
segmentMask：段掩码，散列运算的掩码，=ssize-1

（b)初始化每个segment：
initialCapacity：ConcurrentHashmap初始化容量
loadfactor：每个segment的负载因子
cap：每个segment里hashEntry数组长度，c=initialCapacity/ssize；c>1:取大于等于c的2的n次方；否则为1
threshold：segment的容量，=(int)cap *loadFactor
默认，initialCapacity=16，loadFactor=0.75，cap=1,threshold=0

(c)重写了hash()，减少散列冲突，使散列均匀，提高容器存取效率

(d) segmentFor()：散列算法，定位segment

3、get()方法：
由散列值通过散列运算定位到segment，再由散列算法定位到元素

public  V get(Object key){
     if(key==null)  throws NullPointerException;
     int hash=hash(key);  //再散列
     return  segmentFor(hash).get(key,hash);   //由散列值通过散列运算定位到segment(segmentFor())，再由散列算法定位到元素(这里又调用了segment的get()方法去获取元素)

segment的get()方法：先用hash值定义到这个segment中的HashEntry[]数组中的位置，然后再去这个HashEntry的链表比较key

V get(Object key, int hash) {
        if (count != 0) { // read-volatile // ①
            HashEntry<K,V> e = getFirst(hash); 
            while (e != null) {
                if (e.hash == hash && key.equals(e.key)) {
                    V v = e.value;
                    if (v != null)  // ② 注意这里
                        return v;
                    return readValueUnderLock(e); // recheck
                }
                e = e.next;
            }
        }
        return null;
}

get()过程不加锁，因为所有使用的共享变量都是volatile类型，保持可见性，能被多线程同时读，保证不读到过期值(因为java内存模型的happen before元组，volatile字段写先于读，即使两个线程同时读改，get也能得到最新值)

注意定位hashEntry和定位segment的散列算法！！
但 segment：元素原哈希码 再散列 得到的值 的高位 &(segment数组长度-1)
hashEntry：元素原哈希码 再散列后的值 &(hashEntry数组长度-1)

4、put()：要加锁。
由散列值通过散列运算定位到segment，再在segment中插入操作。
（1）先判断是否需要扩容，扩容是创建一个容量是原来两倍的数组，将原数组元素 再散列 后插入到新数组；注意只对某个segment单独扩容。
（2）定位添加元素的位置，再放入HashEntry数组中

五、LinkedHashMap：继承于HashMap，=散列数组+循环双向链表

1、重要字段：
trasient：防止序列化

transient  LinkedHashMap.Entry<K,V> head;  //链表头结点（空节点）
transient  LinkedHashMap.Entry<K,V> head;  //链表尾节点
final boolean accessOrder；  //表示迭代顺序，true表示访问顺序，false是插入顺序，默认false。final字段，只能在构造方法中传入

2、构造方法：初始容量，负载因子

    /*生成一个空的LinkedHashMap,并指定其容量大小和负载因子，
     * 默认将accessOrder设为false，按插入顺序排序
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
    生成一个空的LinkedHashMap,并指定其容量大小，负载因子使用默认的0.75，
     * 默认将accessOrder设为false，按插入顺序排序*/
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    /**
     * 生成一个空的HashMap,容量大小使用默认值16，负载因子使用默认值0.75
     * 默认将accessOrder设为false，按插入顺序排序.
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    /**
     * 根据指定的map生成一个新的HashMap,负载因子使用默认值，初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)
     * 默认将accessOrder设为false，按插入顺序排序.
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

    /**
     * 生成一个空的LinkedHashMap,并指定其容量大小和负载因子，
     * 默认将accessOrder设为true，按访问顺序排序
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

3、get()：
通过key获取value，与hashmap的区别是：当LinkedHashMap按访问顺序排序的时候，会将访问的当前节点移到链表尾部(头结点的前一个节点)

六、HashSet：底层是HashMap，继承于AbstractSet
Set<E> set=new HashSet<>();
底层是HashMap（直接使用HashMap），是无序的，非线程安全，可以存储null
元素无序：因为底层hashmap，本身是散列存放，所以hashset也无序
元素不能重复：底层hashmap中key不能重复，会新value取代旧的，所以hashset也不能重复

1、HashSet具体结构：

image.png

public class HashSet<E>  extends AbstractSet<E>
                   implements  Set<E>，Cloneable，java.io.Serializable

继承了abstractSet，能使用clone()、能使之序列化

2、构造方法：(5个：4个public 加1个 default的方法(即只能包可见，是给HashSet的子类LinkedHashSet使用)）
主要就是构造一个HashMap，默认初始容量16，加载因子0.75

//默认的构造hashset，就是调用hashmap的默认构造函数，16，0.75
public HashSet(){
       map=new  HashMap<>();     
}

//传入一个collection，转为hashset
public  HashSet(Collection<? extends E> c){
      map=new HashMap<>(Math.max((int)(c.size()/.75f)+1,16));
      addAll(c);
}

/*自动规定初始化容量和加载因子大小，实际上调用了hashmap的
构造函数，在这就是生成一个初始化容量>规定初始化容量的最小的2的n次幂，
加载因子不变
*/
 public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

/*自规定初始化容量，也是生成一个初始化容量>规定初始化容量的最小的2的
n次幂，加载因子用默认的0.75
*/
 public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

/*default的构造方法，给hashset的子类linkedhashset使用，底层实现原理
是LinedHashMap而不是HashMap*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

3、boolean add(E)：
Hashset添加元素会去重，因为hashSet的底层是hashmap，hashmap也是去重的，它遇到相同的Key会新值取代旧值，而key不变，所以set也不能重复。

PRESENT：这是一个假的值，这是为了符合map的put方法是要同时put key和value的，而set只有key没有value，所以需要一个假的值，是Object类型的。

add()返回一个boolean，map的put方法是【先用key(hash()：return key==null?0:((h=key.hash())^(h>>16))得到key的hash值，找数组中的位置(indexFor()：h&(length-1))，再去该位置的链表查找有没有相同的key（equals())，有则新值取代旧值，返回旧值；无则返回null】，或者key为null，返回null，所以这里判断返回的是否为null，才能判断是否有相同的key。这里的add()也变相的判断了key是否为null和key是否有重复的。

//假的值，为了符合map的put(key,value)
private   static final  Object PRESENT= new Object();
public boolean add(E e){
       return map.put(e,PRESENT)==null;
}

4、boolean remove(E):
同样是因为hashmap中的V remove(key)方法，是通过找数组，找链表，去找这个key，有则链表删除，修改前一节点的next指向后一节点；有该key，则返回value，无则返回null。

public  boolean remove(E e){
     return map.remove(e)==PRESENT;
}

5、其他方法：
public boolean contains(Object o)：调用了map的conainsKey(o)
public boolean isEmpty()：调用了map的isEmpty()
public int size()：调用了map.size()
遍历：
Map<Integer> map=new HashMap<>();
for(Integer value:map){
输出value;
}

七、LinkedHashSet：继承于HashSet，底层是LinkedHashMap

image.png

1、构造函数：基本上是调用了父类hashset中一个defalut专门用于Linkedhashset进行调用的构造函数，该构造函数底层不是hashmap，而是LinkedHashMap。代码如下：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
     map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
 }

在LinkedHashSet的4个构造函数中都调用了以上这个父类的构造方法

public class LinkedHashSet<E>
  extends HashSet<E>
  implements Set<E>, Cloneable, Serializable
{
  private static final long serialVersionUID = -2851667679971038690L;
  
  public LinkedHashSet(int paramInt, float paramFloat)
  {
    super(paramInt, paramFloat, true);
  }
  
  public LinkedHashSet(int paramInt)
  {
    super(paramInt, 0.75F, true);
  }
  
  public LinkedHashSet()
  {
    super(16, 0.75F, true);
  }
  
  public LinkedHashSet(Collection<? extends E> paramCollection)
  {
    super(Math.max(2 * paramCollection.size(), 11), 0.75F, true);
    addAll(paramCollection);
  }
  
  public Spliterator<E> spliterator()
  {
    return Spliterators.spliterator(this, 17);
  }
}

/* Location:           D:\Java\jre 1.8.0_171\lib\rt.jar
 * Qualified Name:     java.util.LinkedHashSet
 * Java Class Version: 8 (52.0)
 * JD-Core Version:    0.7.1
 */

LinkedHashSet的源码jdk1.8只有以上的源码。

八、hashCode()和equals()
重写了equals方法的对象必须同时重写hashCode()方法。
1、hashCode是根类Obeject中的方法，返回对象的哈希码值。默认情况下，Object中的hashCode() 直接返回对象的32位jvm内存地址。
如果两个对象相同，则其hashCode值一定相同；如果两个对象的hashCode相同，它们不一定相同。
String、HashMap重写了hashCode()方法。
（1）String的重写：用 String 的 char 数组的数字每次乘以 31 再叠加最后返回。

public  int hashCode(){
       int h=hash;
       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;
}

2、equals只能比较引用类型，比较引用类型的值。
==：基本类型比较两个变量的值；引用类型比较两个变量在堆中存储的地址是否相同，及栈中的内容是否相同。
equals：比较两个变量是否是对同一个对象的引用，即堆中的内容是否相同

（a）Object类：只能判断同一，即判断这两个引用对象指的是一个对象。
public boolean equals(Object x){
return this==x;
}

（b）在String中，
（1）==先比较地址，如果是同一对象的引用，则相等，返回true;
（2）如果不是同一对象，equals方法挨个比较两个字符串对象内char[]的字符，完全相等返回true

String类和Date类都重写了equals方法

九、String类的源码：
https://blog.csdn.net/ylyg050518/article/details/52352993
String类被final修饰，String对象是不可变类，是线程安全的。

1. 成员变量
   String类中包含一个不可变的char数组用来存放字符串，一个int型的变量hash用来存放计算后的哈希值。不允许直接访问成员,只能赋值一次，对变量无setter方法。
   注意String类存字符串用的是char[]数组！！！String类是final的！！成员变量都是私有的private的！final的！！！

//用于存储字符串
private final char value[];

//缓存String的hash值
private int hash; // Default to 0

/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = -6849794470754667710L;

构造函数：

//不含参数的构造函数，一般没什么用，因为value是不可变量
public String() {
    this.value = new char[0];
}

//参数为String类型
public String(String original) {
    this.value = original.value;
    this.hash = original.hash;
}

//参数为char数组，使用java.utils包中的Arrays类复制
public String(char value[]) {
    this.value = Arrays.copyOf(value, value.length);
}

//从bytes数组中的offset位置开始，将长度为length的字节，以charsetName格式编码，拷贝到value
public String(byte bytes[], int offset, int length, String charsetName)
        throws UnsupportedEncodingException {
    if (charsetName == null)
        throw new NullPointerException("charsetName");
    checkBounds(bytes, offset, length);
    this.value = StringCoding.decode(charsetName, bytes, offset, length);
}

//调用public String(byte bytes[], int offset, int length, String charsetName)构造函数
public String(byte bytes[], String charsetName)
        throws UnsupportedEncodingException {
    this(bytes, 0, bytes.length, charsetName);
}

2、String常用方法
（1）boolean equals(Object obj1)
重写了Object的equals方法。先比较内存地址，即引用(==)；再比较两个对象的value值,char[]单个字符从后往前比较
//先比较内存地址是否相同，即比较引用的是否同一个对象(用==比较引用，原对象==比较对象)，是则返回真
//如果比较对象不是String类型的数据，返回假
//比较对象是String类型，则要比较两个对象的值；即比较两个对象的value(底层是char数组），先比较两个char数组长度是否相等，相等再从后往前单个字符判断字符是否等，有不相等，返回false；每个字符都相等，返回true

public boolean  equals(Object  obj1){
        //比较引用
       if(this==obj1)  return true;

        //比较对象是否为String类型
       if(obj1 instanceof  String){
               String  s1=(String)obj1;   //比较对象先变回String类型
                int n=value.length;  //原对象长度

                //比较两者的char数组长度
                if(n==s1.value.length){
                      char[] v1=value;   //原对象的字符串
                      char[] v2=s1.value;  //比较对象的字符串
                       int  i=0;
                       //从后往前单个字符判断，不相等，返回false
                        for(int i=n-1;i>=0;i--){
                              if(v1[i]!=v2[i])    return false;
                          }
                       return true;
                  }
       }
     return false;
}
 

（2）int hashCode()
String类重写了hashCode()方法，采用多项式计算的来，
两个String一样，则hashCode相同；
两个String对象的hashCode相同，不代表String一样。

String对象的哈希码计算公式：s[0]31^(n-1)+s[1]31^(n-2)+...+s[n-1]
空字符串哈希值为0

public int hashCode() {
    int h = hash;
    //如果hash没有被计算过，并且字符串不为空，则进行hashCode计算
    if (h == 0 && value.length > 0) {
        char val[] = value;

        //计算过程
        //s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        //hash赋值
        hash = h;
    }
    return h;
}

（3）int compareTo(String anotherString)
先找出较短字符串长度lim，从第一个字符到最小长度lim处为止，不等则返回自身，全都等，返回len1-len2

public int compareTo(String anotherString) {
   //自身对象字符串长度len1
   int len1 = value.length;
   //被比较对象字符串长度len2
   int len2 = anotherString.value.length;
   //取两个字符串长度的最小值lim
   int lim = Math.min(len1, len2);
   char v1[] = value;
   char v2[] = anotherString.value;

   int k = 0;
   //从value的第一个字符开始到最小长度lim处为止，如果字符不相等，返回自身（对象不相等处字符-被比较对象不相等字符）
   while (k < lim) {
       char c1 = v1[k];
       char c2 = v2[k];
       if (c1 != c2) {
           return c1 - c2;
       }
       k++;
   }
   //如果前面都相等，则返回（自身长度-被比较对象长度）
   return len1 - len2;
}

（4）
public boolean startsWith(String prefix , int toffset) ：
参数表示的字符序列是此对象从索引toffset处开始的子字符串，则返回true；否则返回false。
public boolean startsWith(String prefix) ：
返回值：如果参数表示的字符序列是此字符串表示的字符序列的前缀，则返回true；否则返回false。

以此类推 endsWith() 和 endsWith(String value)

起始比较和末尾比较都是比较经常用得到的方法，例如在判断一个字符串是不是http协议的，或者初步判断一个文件是不是mp3文件，都可以采用这个方法进行比较。

public boolean startsWith(String prefix, int toffset) {
    char ta[] = value;
    int to = toffset;
    char pa[] = prefix.value;
    int po = 0;
    int pc = prefix.value.length;
    // Note: toffset might be near -1>>>1.
    //如果起始地址小于0或者（起始地址+所比较对象长度）大于自身对象长度，返回假
    if ((toffset < 0) || (toffset > value.length - pc)) {
        return false;
    }
    //从所比较对象的末尾开始比较
    while (--pc >= 0) {
        if (ta[to++] != pa[po++]) {
            return false;
        }
    }
    return true;
}

public boolean startsWith(String prefix) {
    return startsWith(prefix, 0);
}

public boolean endsWith(String suffix) {
    return startsWith(suffix, value.length - suffix.value.length);
}

（5）String concat(String str)：字符串连接。
先判断被添加字符串是否为空来决定要不要创建新的对象。
为空返回对象本身，不为空通过新创建字符数组==>新字符串对象

public  String  concat(String str){
       int otherLen=str.length();
       //如果被添加的字符串为空，返回对象本身
      if(otherLen==0)   return this;

      int len=value.length   //当前对象的字符串char数组的长度
      char buf[]=Arrays.copyOf(value,len+otherLen);  //创建一个新的char[]字符数组，先存储原字符串的值，字符数组大小为len+otherLen
      str.getChars(buf,len);    //将对象字符串str的所有字符复制到目标字符数组的buf的第len位开始  。
//原函数是java1.6的String类的方法  将字符串从srcBegin到srcEnd位置的字符复制到目标字符数组dst的第dstBegin位置，public void getChars(int srcBegin, int srcEnd, char[] dst,  int dstBegin)   
       return new String(buf,true)；//返回一个新的对象
}

（6）String replace(char oldChar,char newChar)：
新值取代旧值

public String replace(char oldChar, char newChar) {
    //新旧值先对比
    if (oldChar != newChar) {
        int len = value.length;
        int i = -1;
        char[] val = value; /* avoid getfield opcode */

        //找到旧值最开始出现的位置
        while (++i < len) {
            if (val[i] == oldChar) {
                break;
            }
        }
        //从那个位置开始，直到末尾，用新值代替出现的旧值
        if (i < len) {
            char buf[] = new char[len];
            for (int j = 0; j < i; j++) {
                buf[j] = val[j];
            }
            while (i < len) {
                char c = val[i];
                buf[i] = (c == oldChar) ? newChar : c;
                i++;
            }
            return new String(buf, true);
        }
    }
    return this;
}

（7）public String trim() 删除头尾空白符的字符串。
找到字符串前段没有空格的位置st，字符串后段没有空格的位置len，
如果都没有空格，返回字符串本身，否则取st到len的字符串

public String trim() {
    int len = value.length;
    int st = 0;
    char[] val = value;    /* avoid getfield opcode */

    //找到字符串前段没有空格的位置
    while ((st < len) && (val[st] <= ' ')) {
        st++;
    }
    //找到字符串末尾没有空格的位置
    while ((st < len) && (val[len - 1] <= ' ')) {
        len--;
    }
    //如果前后都没有出现空格，返回字符串本身
    return ((st > 0) || (len < value.length)) ? substring(st, len) : this;
}

（8）其他方法：

public int length() {
    return value.length;
}
public String toString() {
    return this;
}
public boolean isEmpty() {
    return value.length == 0;
}
public char charAt(int index) {
    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

（9）其他类型转换为String类型：
String.valueOf(a) a可以是boolean类型、char、char[]、int、long、double、float、甚至是Object类
则转换后输出s，也会得到原值【char[] ch={‘a','b','c','d'}；】
但不可以是int[],double[]...这些用这个方法不会报错，但输出s是类似哈希值的东西（地址）

（10）数组复制：一个数组直接复制到另一个数组
System.arraycopy（原数组，原数组复制位置，新数组，新数组复制位置，复制串长度）

System.arraycopy(digits,0,res,1,digits.length);

（11）String s="abc"; 创建了2个对象，一个是abc，放在常量池中（方法区），一个是s，在栈
String s=new String("abc"); 创建3个对象；一个是abc，放在常量池；s放在栈；new String 创建新对象在堆中。

（12）注意：
1、String和包装类是不可变类，是线程安全的。
对于 String s="abc"; s="def"； 这里的s是字符串对象“abc”的引用，引用是可变的，和对象实例的属性变化没关系。

2、String不可变的原因：设计考虑、效率优化问题、安全性
（1）设计考虑：字符串常量池的需求（常量池是方法区的一部分，线程共享）
当创建一个String对象时,假如此字符串值已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。

String s1 = "abcd"; 
String s2 = "abcd"; 

以上实则只会在堆中产生一个实际String对象。如果字符串对象是可变的，就会导致逻辑错误，改变一个对象会影响另一个对象。这种常量池的思想，是一种优化手段。

（2）效率优化问题：
字符串中String对象的哈希码被频繁使用，比如在hashmap容器中，而字符串的不变性也保证了hash码唯一性，可放心进行缓存。是一种性能优化手段，不必每次都去计算新的哈希码。

（3）安全性：
String被许多java类库当作参数，如网络连接地址URL，文件路径path，反射机制所需的Sstring参数等，如果可变，会引起安全隐患。

（4）字符串不可变，所以是线程安全的，同一个字符串实例可被多线程共享，不用使用同步。

六、Stack：通过数组
peek()：返回栈顶
pop()：出栈
push()：入栈