Map、List底层实现原理

---

原理至上

一：Map

特点：双列数据，存储Key-Value对的数据

解释：使用Set存储，保证key是无序的且唯一，value可重复，无序（Collection），再使用put放数据时，map中封装了底层使用的是entry中的key和value俩属性 ，并且Map中的key不能对应多个value值

结构理解：

• Map中的key：无序、不可重复的，相当于使用Set存储所有的key —> 如果map中的key是自定义的，那么key所在类需重写equals()和hashCode()方法，（以hashMap为例）
• Map中的value()：无序、可重复的，相当于使用Collection存储所有的value —>如果map中的value是自定义的，那么key所在类需重写equals()，不需要重写hashCode()方法，主要是在存储的时候，效率高，查询方便
• 一个键值对key-value构成一个Entry对象
• Map中的Entry：无序、不可重复的，使用Set存储所有的Entry

实现类：

（主要实现类）HashMap、TreeMap、HashTable

HashMap：

定义：线程不安全，效率高，可以存储键值对为Null的数据

JDK7之前使用–>数组 链表

JDK8–>数组 链表 红黑树

底层实现原理：

---

JDK1.7为基础说明：

HashMap map = new HashMap();

以空参构造器创建HashMap对象，在实例化后，底层创建了长度为16的一维数组，数组类型为Entry[] 数组名table，传入数据map.put(key1,value1);

• 首先，调用key1所在类的hashCode()方法，通过某种算法（indexfor）计算key1的哈希值，得到在Entry数组中的存放位置
• 如果得到的key1的哈希值位置上数据为空，则Entry添加成功 【情况一】
• 如果得到的key1的哈希值位置上数据不为空，（意味着此位置存在一个或多个数据（以链表形式存在）），比较key1和已经存在的一个或多个数据的哈希值
  1. 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功 【情况二】
  2. 如果key1的哈希值和已经存在的某一个数据（key2-value2）的哈希值相同，则继续比较：调用key1所在类的equals()方法与key2作比较：

如果equals()返回false，此时key1-value1添加成功。【情况三】

如果equals()返回true，使用value1替换value2。

补充：关于【情况二】和【情况三】，此时的key1-value1和原来的数据以链表的方式存储，并且在不断的添加数过程中，会涉及到扩容问题，默认的扩容方式为原来的2倍，并且将原来的数据复制过来

---

JDK8相比较与JDK7在底层实现方面的不同：

1. new HashMap();底层没有创建一个长度为16的数组
2. JDK8底层的数组是：Node[]，而非Entry[]
3. 首次调用put()方法是，底层创建长度为16的数组
4. JDK7底层结构只有：数组 链表。JDK8中底层结构：数组 链表 红黑树。并且当数组的某一个索引位置的元素以链表形式存在的数据个数 > 8 且当前的数组长度 > 64 时，此时此索引位置上的所有数据改为使用红黑树存储，如果< 64 则加载扩容方法

DEFALT_INITIAL_CAPCITY：HashMap的默认容量：16

DEFAULT_LOAD_FACTOR:HashMap的默认加载因子：0.75

threshold：扩容的临界值：容量加载因子：160.75 => 12

TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树：8

MIN_TREEIFY_CAPAACITY：桶中的Node被树化时最小的hash表容量：64

临界值：数组长度*加载因子=12，当存储个数超过12，就开始扩容

为什么要提前扩容？为什么不等容量满了之后再扩？

不一定会满，因为在存储数据时，是根据hash值调用indexfor方法来计算数存储位置，并且数据存储过程中还会形成链表存储，提前扩容是为了尽可能出现链表的情况少一些，而加载因子就要随着减小，一旦加载因子减小，数组的利用率下降。如果加载因子增大，链表出现的情况增多，数组的查询效率降低，时间复杂度随之升高

---

比如：在登录界面需要输入用户名和密码进行登录，用户名和密码存储在map中，通过俩个键值对，用户名和密码进行数据库校验，如果有一个未输入，数据存储HashTable中，则会报空指针异常

—>

（指针）LinkedHashMap****

底层实现原理：

理解：形成链表，保证在遍历map元素时，可以按照添加的顺序实现遍历

原因：在原有的hashMap底层结构基础上，添加一对指针，指向前一个和后一个元素，对于频繁的遍历操作，实现该类，效率高于HashMap

TreeMap：

理解：存储有序键值对，相当于TreeSet，保证按照添加的key-value对进行排序，实现排序遍历，按照key进行自然排序或定制排序，底层使用的是红黑树（TreeSet），如果map中的key是自定义的，需自然排序或定制排序

HashTable:

理解：古老实现类（1.0时期），线程安全。效率低，涉及到数据修改时，都会有synchronized修饰，不可以存储Null的Key和Value

—>

Properties

定义：常用来处理配置文件，key和value都是String类型

面试题：

1、HashMap的底层实现原理

2、HashMap和Hashtable的异同

3、CurrentHashMap和Hashtable的异同

二：冒泡排序

思想：排序序列从前往后，依次比较相邻元素的排序码，若为逆序，则交换，使排序码较大的元素从前往后移

string类型如何排序：

• 如果string中的元素是英文，则使用字母顺序进行排序
• 如果为中文，则使用中文的Unicode值进行排序
• 如果是对象，则通过其中某一个属性进行排序

三：List

1、特点：

1. 存储元素有序、且可重复（又称动态数组），每个元素都有对应的顺序索引
2. List容器中的元素都对应一个证书型的序号记载其在容器中的位置，根据序号取元素
3. JDK API中list接口的实现类常用的有：ArrayList、LinkedList、Vector

2、实现类：

1. ArrayList（JDK1.2时期）：作为List接口的主要实现类：线程不安全，但效率高，底层使用Object[] elementData存储
2. LinkedList（JDK1.2时期）：线程不安全，对于频繁的插入、删除操作效率比ArrayList高，底层使用双向链表存储
3. Vector：List接口的古老实现类（JDK1.0时期），线程安全，效率低，底层同样使用Object[] elementData存储

3、面试题

ArrayList、LinkedList、Vector三者的异同？

同：三个类都实现了List接口，存储有序的、可重复的数据

不同：ArrayList：线程不安全，但效率高。LinkedList：线程不安全，对于频繁的插入、删除操作效率比ArrayList高，底层使用双向链表存储。Vector：线程安全，效率低

4、源码分析

1. ArrayList源码分析： JDK 7为例

   • 创建ArrayList list = new ArrayList();底层会初始化一个长度为10的数组Object[] elementData

   • 如果添加的数据超过数组容量，则扩容，默认情况下，扩容为原来的1.5倍，在超过扩容后的数组容量，则使用当前的数组容量，若是超过了当前容量，则将整形的最大值作为最大容量，否则报错
     

   • 建议使用带参构造器

   • ArrayList list = new ArrayList(int capacity);
     

JDK 8 为例

• 创建ArrayList list = new ArrayList()；底层数组Object[] elementData初始化为‘{}’

• 在调用list.add()；方法时，底层才会创建长度为10的数组，并且将数据添加到数组Object[] elementData（顺序表）中

• 在后续的添加和扩容操作上，与JDK 7无异

---

小结：JDK 7中的ArrayList的对象的创建类似于单例模式的饿汉式，创建数组即开辟数组空间.。JDK 8中的ArrayList的对象的创建类似于单例模式的懒汉式，延迟了数组的创建，节省内存空间。

---

2.LinkedList源码分析：

• LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素，同时定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了俩变量，prev变量记录前一个元素的位置，next变量记录下一个元素的位置
  

• LinkedList list = new LinkedList();内部声明Node类型的first和last属性，默认值为null

• 在调用add方法之后，才创建Node对象，其中Node的定义也体现了LinkedList的双向链表的说法
  

3.Vector源码分析：

• JDK 7 和JDK 8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组，在扩容方面，默认扩容为原来的数组长度的2倍

四:String

定义：String字符串，使用—""—引起来表示

特性：

1. String声明为final，不可被继承
2. String实现了Serializable接口：表示字符串是支持序列化的，实现了Comparable接口：表示String可以比较大小
3. String内部定义了final char[] value用于存储字符串数据
4. String：代表不可变的字符序列

–尚未完成！敬请期待！

这篇好文章是转载于：学新通技术网