集合框架及背后的数据结构

1.介绍：

Java 集合框架，又被称为容器是定义在 java.util 包下的一组接口 interfaces 和其实现类 classes 。
其主要表现为将多个元素置于一个单元中，用于对这些元素进行快速、便捷的存储、检索 、管理 ，即平时我们俗称的增删查改 CRUD 。

2.类和接口总览

3.学习的意义 

• 使用成熟的集合框架，有助于我们便捷、快速的写出高效、稳定的代码
• 学习背后的数据结构知识，有助于我们理解各个集合的优缺点及使用场景
   

 4.常见面试题

HashMap 了解不，介绍一下，如果一个对象为 key 时，hashCode 和 equals 方法的用法要注意什么？

先说一下equals方法和hashcode的关系

• 如果两个对象equals相等，那么这两个对象的hashcode一定也相同
• 如果两个对象的hashcode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置(放在同一个篮子里)

在HashMap中的比较key是这样的，先求出key的hashcode(),比较其值是否相等，若相等再比较equals(),若相等则认为他们是相等的。若equals()不相等则认为他们不相等。

所以想以对象作为HashMap的key，必须重写该对象的hashCode和equals方法。确保hashCode相等的时候equals的值也是true。

Student st1 = new Student("wei","man");

Student st2 = new Student("wei","man"); 

正常理解这两个对象再存入到hashMap中应该是相等的，但如果你不重写 hashcode（）方法的话，比较是其地址，不相等！

HashMap中的比较key是这样的，先求出key的hashcode(),比较其值是否相等，若相等再比较equals(),若相等则认为他们是相等 的。若equals()不相等则认为他们不相等。如果只重hashcode()不重写equals()方法，当比较equals()时只是看他们是否为 同一对象（即进行内存地址的比较）,所以必定要两个方法一起重写。HashMap用来判断key是否相等的方法，其实是调用了HashSet判断加入元素 是否相等。

HashSet 和 HashMap 的区别是什么？

1.hashset实现了set接口，它不允许集合中出现重复元素，当我们提到hashset的时候，第一件事就是在将对象存储在hashset之前，要确保重写hashCode()方法和equals方法，这样才能比较对象的值是否相等，确保集合中没有存储相同的对象，如果不重写上述两个方法，那么将使用下面方法默认实现：public boolean add(Object obj)方法用在Set添加元素时，如果元素值重复时返回“false”，如果添加成功则返回"true".

2.hashmap实现了map接口，map接口对键值对进行映射，map中不允许出现重复的键，map接口有俩个基本的实现treemap,hashmap,treemap保存了对象的排列次序，而hashmap不能，hashmap可以有空的键值对，hashmap是非线程安全的，要想实现线程安全，那么需要调用collections类的静态方法synchronizedMap（）实现。      

HashMap 是线程安全的么？那需要线程安全需要用到什么？

精讲

hashmap线程不安全 线程安全的替代方案有：

HashTable,Collections.synchronizedMap,ConcurrentHashMap

hashtable,在get，put方法加了synchronized，hashtable是通过synchronized来实现线程安全的。

synchronizedMap的使用：

//实例化一个HashMap对象，该对象是非线程安全的
Map map = new HashMap();
//实例化一个SynchronizedMap对象，该对象是线程安全的
//将非线程安全的map对象传入到线程安全的SynchronizedMap对象中
SynchronizedMap synchronizedMap = new SynchronizedMap(map);
//底层通过synchronized保证了线程安全
synchronizedMap.put("author", "技术笔记");

Collections.synchronizedMap方法的实现很简单，该方法是一个静态方法，封装了装饰器类SynchronizedMap的创建逻辑，使方法的调用者无需了解底层的具体实现，从而简化了编程。Collections.synchronizedMap方法使用了装饰器模式为线程不安全的HashMap提供了一个线程安全的装饰器类SynchronizedMap，通过SynchronizedMap来间接的保证对HashMap的操作是线程安全，而SynchronizedMap底层也是通过synchronized关键字来保证操作的线程安全

ConcurrentHashMap,ConcurrentHashMap的put方法使用了cas+syncronized保证了添加键值对数据的原子性.ConcurrentHashMap也使用了volatile保证了共享变量的内存可见性.

ArrayList 和 LinkedList 的区别是什么？

• arraylist是基于动态数组实现的集合，linkedlist是基于链表实现的集合，
• 对于随机访问的index下标元素，get（查），set（改）操作，arraylist直接使用下标找到元素，而linkedlist需要指针遍历元素，arraylist要比linkedlist快.
• add(增)，del（删），arraylist在新增元素的时候可能进行扩容和复制数组，linkedlist只需要修改指针即可。      
• linkedlist不适合高效的随机访问

有了解过 HashMap 的具体实现么？

HashMap 和 ConcurrentHashMap 哪个效率更高？

判断一个链表是否是一个回文链表。

hashCode 主要是用来做什么用的？

1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；

2、如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；

3、两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。

1.hashcode是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有

例如内存中有这样的位置
0  1  2  3  4  5  6  7  
而我有个类，这个类有个字段叫ID,我要把这个类存放在以上8个位置之一，如果不用hashcode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。

2.但是如果两个类有相同的hashcode怎么办那（我们假设上面的类的ID不是唯一的），例如9除以8和17除以8的余数都是1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals了。
也就是说，我们先通过 hashcode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals()，为什么还要重写hashCode()呢？
想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写hashcode()来找到桶，光重写equals()有什么用啊

 

5.接口

Collection ：用来存储管理一组对象 objects ，这些对象一般被成为元素 elements
 

• 1. Set : 元素不能重复，背后隐含着查找/搜索的语义
• 2. SortedSet : 一组有序的不能重复的元素
• 3. List : 线性结构
• 4. Queue : 队列
• 5. Deque : 双端队列
• 6.Map : 键值对，背后隐含着查找/搜索的语义
• 7.SortedMap : 一组有序的键值对
   

6.Collection 接口

Collection 常用方法

Collection 代码示例：

package test1;import java.util.ArrayList;
import java.util.Collection;public class Test1 {public static void main(String[] args) {Collection<String> collection = new ArrayList<>();collection.add("h");collection.add("e");collection.add("l");collection.add("l");collection.add("o");for (String str : collection) {System.out.print(str);}System.out.println();System.out.println(collection.size());collection.clear();System.out.println(collection.size());}
}

 7.Map 接口

Map 常用方法说明：

Map 代码示例：

package test1;import java.util.HashMap;
import java.util.Map;public class Test2 {public static void main(String[] args) {Map<String, String> map = new HashMap<>();System.out.println(map.size());System.out.println(map.isEmpty());System.out.println(map.get("罗贯中"));System.out.println(map.getOrDefault("罗贯中", "空"));System.out.println(map.containsKey("罗贯中"));System.out.println(map.containsKey("曹雪芹"));map.put("罗贯中", "三国演义");map.put("曹雪芹", "红楼梦");System.out.println(map.size());System.out.println(map.isEmpty());System.out.println(map.get("罗贯中"));System.out.println(map.get("曹雪芹"));System.out.println(map.containsValue("红楼梦"));for (Map.Entry<String, String> entry : map.entrySet()) {System.out.print(entry.getKey() + " ");System.out.print(entry.getValue());System.out.println();}}
}

 

8.实现类

 

9.还要学习的知识点：

• 1. Collection
• 2. List
• 3. ArrayList
• 4. LinkedList
• 5. Stack
• 6. Queue
• 7. PriorityQueue
• 8. Deque
• 9. Set
• 10. HashSet
• 11. TreeSet
• 12. Map
• 13. HashMap
• 14. TreeMap
• 15. Collections