JAVA常用数据结构及原理分析

集合父接口Collection，Map和集合工具类Collections

集合框架Collection的三种主要实现如下：List(列表)，Set（散列集，有一个key-value的Map进行维护，其中key值保证Set集合里元素的唯一性），Queue（队列，先进先出，底层实现可以用List列表或者LinkedList链表）

集合框架的另外一种数据类型的总接口是Map，基于Key-Value进行存储数据的，其中Key键值是不可重复的，主要是通过类的hashCode()和equal()进行保证的

Collections，它封装了所有集合的关于算法操作的具体实现静态方法：二分查找，找出集合最大值，集合最小值，打乱集合，以及生成不可修改集合，同步集合（多线程环境下使用），其主要方法API如下：

由于大部分的集合接口实现类都是不同步的，可以使用Collections.synchronized*方法创建同步的集合类对象。
如创建一个同步的List：
List synList = Collections.synchronizedList(new ArrayList());
其实现原理就是重新封装new出来的对象，操作对象时用关键字synchronized同步。看源码很容易理解。
Collections部分源码：

//Collections.synchronizedList返回的是静态类SynchronizedCollection的实例，最终将new出来的ArrayList对象赋值给了Collection<e> c。
static class SynchronizedCollection<e> implements Collection<e>, Serializable {
 
         final Collection<e> c;  // Backing Collection
         final Object mutex;     // Object on which to synchronize
 
         SynchronizedCollection(Collection<e> c) {
             if (c== null )
                 throw new NullPointerException();
             this .c = c;
             mutex = this ;
         }
         //...
         public boolean add(E e) {
             //锁定信号量才可以对集合进行操作，在多线程环境下来进行同步,调用的还是原来的方法
             //操作集合时简单调用原本的ArrayList对象，只是做了同步
             synchronized (mutex) { return c.add(e);}
         }
         //...
}

List（列表）

List列表允许存储相同元素，插入元素和按照下标获取元素方便，具体实现有ArrayList，LinkedList和Vector，

1. ArrayList底层基于数组实现的，按顺序存储元素以及快速按照元素下标进行获取元素，不可同步的；

2. 而Vector底层也是数组，可进行同步操作，在多线程环境下可以使用；

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //可以看出添加的对象放到elementData数组中去了
    elementData[size++] = e;
    return  true;
}
//ArrayList.remove
public E remove(int index) {
    rangeCheck(index);
 
    modCount++;
    E oldValue = elementData(index);
 
    int  numMoved = size - index - 1;
    if  (numMoved > 0)
        //移除元素时数组产生的空位由System.arraycopy方法将其后的所有元素往前移一位，System.arraycopy调用虚拟机提供的本地方法来提升效率
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work
 
    return  oldValue;
}
 
//Vector add方法上多了synchronized关键字
public  synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return  true;
}

3. LinkedList是链表可以在具体下标位置删除和添加元素，在许多需要根据具体下标添加和删除元素的应用场景下比ArrayList有更好的性能,遍历比线性表慢。

public class LinkedList<e>
extends AbstractSequentialList<e>
implements List<e>, Deque<e>, Cloneable, java.io.Serializable
{
    //头尾节点
    transient  Node<e> first;
    transient  Node<e> last;
}
//节点类
 private  static class  Node<e> {
    //节点存储的数据
    E item;
    Node<e> next;
    Node<e> prev;
    Node(Node<e> prev, E element, Node<e> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Map（存储键值对，key唯一）

HashMap结构的实现原理是将put进来的key-value封装成一个Entry对象存储到一个Entry数组中，位置（数组下标）由key的哈希值与数组长度计算而来。如果数组当前下标已有值，则将数组当前下标的值指向新添加的Entry对象。

public  class HashMap<k,v>
extends AbstractMap<k,v>
implements Map<k,v>, Cloneable, Serializable
{
    transient  Entry<k,v>[] table;
    public  V put(K key, V value) {
        if  (key == null)
            return  putForNullKey(value);
        int  hash = hash(key);
        int  i = indexFor(hash, table.length);
        //遍历当前下标的Entry对象链，如果key已存在则替换
        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))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return  oldValue;
        }
    }
       addEntry(hash, key, value, i);
        return  null;
    }
}
static  class Entry<k,v> implements  Map.Entry<k,v> {
    final  K key;
    V value;
    Entry<k,v> next;
    int  hash;
}

TreeMap是由Entry对象为节点组成的一颗红黑树，put到TreeMap的数据默认按key的自然顺序排序，new TreeMap时传入Comparator自定义排序。

HashMap和TreeMap的区别

（1）HashMap:适用于在Map中插入、删除和定位元素。
（2）Treemap:适用于按自然顺序或自定义顺序遍历键（key）。
（3）HashMap通常比TreeMap快一点（树和哈希表的数据结构使然），建议多使用HashMap,在需要排序的Map时候才用TreeMap.
（4）HashMap 非线程安全 TreeMap 非线程安全
（5）HashMap的结果是没有排序的，而TreeMap输出的结果是排好序的

Set（保证容器内元素唯一性,插入删除效率高）

Set结构其实就是维护一个Map来存储数据的，利用Map结构key值唯一性
HashSet的底层通过HashMap实现的，而HashMap在1.7之前使用的是数组+链表实现，在1.8+使用的数组+链表+红黑树实现。其实也可以这样理解，HashSet的底层实现和HashMap使用的是相同的方式，因为Map是无序的，因此HashSet也无法保证顺序。HashSet的方法也是借助HashMap的方法来实现的。

public  class HashSet<e>
extends AbstractSet<e>
implements Set<e>, Cloneable, java.io.Serializable
{    
 
    //无意义对象来作为Map的value 
    private  static final  Object PRESENT = new  Object();
    public  boolean add(E e) {
        return  map.put(e, PRESENT)==null;
    }
}

TreeSet实现了SortedSet接口，它是一个有序的集合类，TreeSet的底层是通过TreeMap实现的。TreeSet并不是根据插入的顺序来排序，而是根据实际的值的大小来排序。。

数组和链表的区别

不同:

1. 链表是链式的存储结构；数组是顺序的存储结构 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
2. 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；

数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。

相同：
两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

链表是什么

链表是一种上一个元素的引用指向下一个元素的存储结构，链表通过指针来连接元素与元素；链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。

什么是hash碰撞？

HashMap中用的最多的方法就属put() 和 get() 方法；HashMap的Key值是唯一的，那如何保证唯一性呢？我们首先想到的是用equals比较，没错，这样可以实现，但随着内部元素的增多，put和get的效率将越来越低，这里的时间复杂度是O(n)，假如有1000个元素，put时最差情况需要比较1000次。实际上，HashMap很少会用到equals方法，因为其内通过一个哈希表管理所有元素，哈希是通过hash单词音译过来的，也可以称为散列表，哈希算法可以快速的存取元素，当我们调用put存值时，HashMap首先会调用Key的hash方法，计算出哈希码，通过哈希码快速找到某个存放位置（桶），这个位置可以被称之为bucketIndex，但可能会存在多个元素找到了相同的bucketIndex，有个专业名词叫碰撞，当碰撞发生时，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是碰撞时才会执行的方法，所以前面说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出Key是否已存在，如果已存在，则使用新Value值替换旧Value值，并返回旧Value值，如果不存在 ，则存放新的键值对<K, V>到bucketIndex位置。
　　碰撞：多个元素计算得出相同的hashCode，在put时出现冲突。

HashMap 碰撞问题处理：

Java中HashMap是利用“拉链法”处理HashCode的碰撞问题。在调用HashMap的put方法或get方法时，都会首先调用hashcode方法，去查找相关的key，当有冲突时，再调用equals方法。hashMap基于hasing原理，我们通过put和get方法存取对象。当我们将键值对传递给put方法时，他调用键对象的hashCode()方法来计算hashCode，然后找到bucket（哈希桶）位置来存储对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时，他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对。

hashcode是什么？

1. hashcode就是通过hash函数得来的，通俗的说，就是通过某一种算法得到的，hashcode就是在hash表中有对应的位置。
2. hash是一个函数，该函数中的实现就是一种算法，就是通过一系列的算法来得到一个hash值，这个时候，我们就需要知道另一个东西，hash表，通过hash算法得到的hash值就在这张hash表中，也就是说，hash表就是所有的hash值组成的，有很多种hash函数，也就代表着有很多种算法得到hash值，如上面截图的三种，等会我们就拿第一种来说。

本文地址：https://blog.csdn.net/XiaoRenEi/article/details/109563270