ArrayList、LinkedList、HashMap的底层实现

• ArrayList底层的实现就是一个数组（固定大小）,当数组长度不够用的时候就会重新开辟一个新的数组，然后将原来的数据拷贝到新的数组内。
• LinkedList底层是一个链表，是由java实现的双向链表其节点如下

 class{
        private Node privious;  //执行前一个节点
        private Object value;   //当前节点的value值
        private Node next;      //指向下一个节点的值，类似于指针。
}

然后实现增删改查操作，和数据库中链表的增删改查是完全相同的，而且插入是有序的。

• HasgMap底层是一个数组+链表实现。其基本原理是：定义一个LinkedList的数组，然后将数据存储到这个链表数组内。例如：LinkedList[] list = new LinkedList[1000]；这样就定义了一个如下图的数据结构
  

  其中上面一行是一个数组，数组中的一个元素对应一个链表。在插入元素的时候，首先根据key值计算hash值h，然后计算h%1000得到一个数字，然后把该对象插入到对应的数组元素内，如：h%1000得到10，那就将对象插入到list[10]这个链表内。插入的内容是一个数据项，其结构如下：

class{
    private key;
    private value;
}

HashSet底层是通过Map来实现的，Set中不允许有重复的元素，类似于集合，在HashSet的实现的时候，通过Map来实现，每次往Set里添加数据，都会将数据设置为Map的键值，Map的值设置为一个默认值，因为Map的键值不能重复，所以每次添加到Set内的数据也不能重复。