数据结构：

• 线性表：

最常用的、最简单的数据结构，它是n个数据元素的有限序列、

实现线性表：输出存储线性表元素，即是用一组连续的存储单元，依次存储线性表数据元素，另一种是使用链表存储线性表元素，用一组任意的存储单元存储线性表的数据元素（存储单元可以连续，可以不连续）。

• 栈

先进后出

• 队列

一段添加元素。另一端取出元素。入队出队。使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

• 链表

物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个节点，一个是存储元素的数据域（存储空间），另外一个是指向下一个节点的指针域。根据指针的指向，链表形成不同的结构，例如单链表、双链表，循环链表

链表优点：不需要初始化容量，可以任意加减元素，添加或删除元素只需要改变前后两个元素节点的指针域指向地址即可，所以添加，删除很快

缺点：含有大量指针域，占用空间大，需要查找元素需要遍历链表来查找，比较耗时。

使用场景：数据量小，需要频繁增加,删除的操作。

• 树

一种数据结构，由n（n>=1）个有限节点组成的具有层级关系的集合。它看起来像倒挂的树，根朝上，叶朝下，具有以下特点：

每个节点有零个或多个子节点

没有父节点的节点是根节点

每一个非根节有且只有一个父节点

除了根节点，没格子节点可以分为多个不想交的子树。

二叉树，是树中特殊的一种：

每个节点最多有两颗子树，节点的度最多为2

左子树和右子树是有顺序的，次序不能颠倒。

即使某个节点只有一个子树，也要区分左右子树。

二叉树是折中的方案，添加删除元素很快，在查找方面也有自己的算法优化，所以二叉树基友链表的好处，也有数组的好处，是两者的优化方法，在处理大批量动态数据方面非常有用。

拓展：平衡二叉树、红黑树。B+树等。这些数据结构二叉树的基础上衍生了很多功能，在实际应用中广泛用到，例如Mysql索引结构用的是B+树，还有HashMap底层源码是红黑树

目录

数据结构：

Collection接口和Map接口区别：

HashMap 的工作原理是什么？

HashMap的寻址方式

HashSet 的工作原理是什么？

---

：

Collection(源自于java.util.Collection)和Map是java集合框架中两个基本的集合类型，要区别不统集合，首先要从Collection和Map开始。Collection接口是传统的集合接口，可以把单个对象存储起来，而Map接口是映射接口，存储的是键值对。

Collection
List			Set
LinkList	ArrayList	Vector	HashSet	TreeSet	LinkedHashSet

Map
HashMap	HashTable	LinkedHashMap	TreeMap

List(interface)是一种链表， 有序可重复 List可以通过index指导元素的位置，允许重复元素，ArrayList（允许所有元素包括null）   

LinkedList（双向链表结构） 

 Vector可以实现List接口。类似于ArrayList,但是Vector是同步的，由Vector创建的Iterator，虽然和ArrayList是同一接口，但是因为Vector是同步的，当一个Iterator（迭代器）被创建而且正在被使用时，另一个线程改变了Vector的状态（例如删除一些元素），这时调用Iterator方法将抛出ConcurrentModificationException（同事发生）,因此异常必须捕获。

Vector是线程安全的，因为Vector好多方法是sychornized关键字修饰的，比如addElement方法：

Public syschronized void addElement(E obj){

      modCount++;

ensureCapatityHelper(elementCount+1);

elementData[elementCount++]=obj;

}

这样在多线程并发访问Vector实例的时候，保证某一刻最多只有一个线程调用Vector中被syschornized修饰的方法。

反观List，在ArrayList中的add方法：

Public Boolean add(E e){

      ensureCapacityInternal (size+1);

      elementData[size++]=e;

      reture true;

}

有可能同一时候有一个以上线程访问该方法。

我们知道size++运算过程不是原子操作，有可能被中断。那么如果在size++过程中被中断，而另外一个线程恰好执行了一次这样的方法，就会造成脏数据产生。

拓展：什么是原子操作？

原子操作（atomic operation）是不需要syschronized（同步），这是多线程编程老生常谈了，所谓原子操作指的是·不会被线程调度机制打断的操作，这样操作一开始，就一直运行，一直运行到结束，中间不会有任何context switch 切换到另外一个线程。通常所说的原子操作包括对非long和double型的primitive进行赋值，以及返回这两者之外的primitive。之所以要把它们排除在外是因为它们都比较大，而JVM的设计规范又没有要求读操作和赋值操作必须是原子操作（JVM可以试着去这么作，但并不保证）。

如果这个操作所处的层（layer）的更高层不能发现其内部实现与结构，这个操作就是原子操作。

原子操作可以是个步骤，也可以是多个不走，但是其顺序不可以被打乱，也不能被切割，只执行其中一部分。将整个操作作为一个整体是原子性的核心特征。

在单处理器系统中，能够在单条指令中完成的操作就可以认为原子操作，因为中断只能发生在指令之间，这也是CPU指令系统引入的test_and_set  / test_and clear等指令用于临界资源互斥的原因，但是在对称多处理器（Symmetric Multi-Processor）结构中就不同了，由于系统有多个处理器在独立运行，即使在单条指令中完成操作也有可能受到干扰。

如果你代码进程中有多个进程在同时进行，而这些线程可能同时会同时运行这段代码，如果运行结果和单线程运行的结果是一样的，而且其他的变量也和预期值一样，是线程安全的。

或者说:一个类或者程序所提供的接口对于线程来说是原子操作或者多个线程之间的切换不会导致该接口的执行结果存在二义性,也就是说我们不用考虑同步的问题。

线程安全问题都是由全局变量及静态变量引起的。

若每个线程中对全局变量、静态变量只有读操作，而无写操作，一般来说，这个全局变量是线程安全的；若有多个线程同时执行写操作，一般都需要考虑线程同步，否则的话就可能影响线程安全。

比如上例中一个 ArrayList 类，在添加一个元素的时候，它可能会有两步来完成：1. 在 Items[Size] 的位置存放此元素；2. 增大 Size 的值。

在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；

而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。

那好，我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了

也就是说像HashTable和Vector这样的容器实现了线程安全，是通过同步关键字实现的。

此外，我们又注意到，不管是Vector还是List容器，都有可能会出现ConCurrenceModificationException的异常。这是因为几乎所有的集合类都有快速失败的（Fail-Fast）校验机制。这是为了确保集合方法一致而设立的保护措施。他的实现原理就是modCount修改计数器。如在遍历列表的时候（使用迭代器的方式），这时候会保存当前的modCount值，当每次迭代器取值的时候，会通过checkForComodification（）方法来校验modCount是否发生了改变。如果发生了改变，就会抛出ConCurrenceModificationException的异常。

public E next() {

            checkForComodification();

            int i = cursor;

            if (i >= size)

                throw new NoSuchElementException();

            Object[] elementData = ArrayList.this.elementData;

            if (i >= elementData.length)

                throw new ConcurrentModificationException();

            cursor = i + 1;

            return (E) elementData[lastRet = i];

        }

final void checkForComodification() {

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

        }

 那么，即使是使用Vector仍可能会抛出这种异常，这是不是和它声称的线程安全所相悖呢？

其实这里的异常和线程同步是两码事。因为使用迭代器遍历容器的时候，这是记录了modCount值，然后调用了remove方法，这在单线程中本来就是不允许的，和多线程同步没有关系。

线程同步是为了实现线程安全，而在Vector中则是实现了线程的部分安全。

线程安全性不是一个非真即假的命题。 Vector 的方法都是同步的，并且 Vector 明确地设计为在多线程环境中工作。但是它的线程安全性是有限制的，即在某些方法之间有状态依赖(类似地，如果在迭代过程中 Vector 被其他线程修改，那么由 Vector.iterator() 返回的 iterator会抛出ConcurrentModifiicationException。

Set（interface）无序不可重复，HashSet，LinkedHashSet,TreeSet可以实现set接口。Set是一种不包含重复元素的Collection，即任意两个元素e1和e2都是有e1.equals(e2)=false, set最多有一个null元素。因此set的构造函数有一个约束条件，传入的Collection参数不能包含重复元素。但是必须小心操作可变对像（Mutable Object）.如果一个set的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

Map接口：也是接口，但是没有继承collection接口，描述了从不重复的键到值的映射，键值对，

HashMap散列表，基于哈希表实现，就是键值对的映射关系，元素顺序不固定，适合对元素插入删除定位等操作。

TreeMap：红黑树实现，TreeMap的元素保持着某种固定的顺序，更加适合对元素的遍历。

Iterator接口：所有实现Iterator接口方法能以迭代方式逐个访问集合中的各元素，并可以从Collection中除去适当的元素。

Iterator it=a.iterator();

        while (it.hasNext()){

           String ob=(String)it.next();

            System.out.println(ob);

        }.

Hsahtable类：继承Map接口，实现key-value的哈希表。HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。

      Comparable接口：可用于比较的实现，可以实现compareTo方法。Entity层实现Comparabel接口

====原理

HashMap是非线程安全的。而HashMap的线程不安全主要体现在resize时的死循环

HashMap 的工作原理是什么？

我们知道在 Java 中最常用的两种结构是数组和模拟指针（引用），几乎所有的数据结构都可以利用这两种来组合实现，HashMap 也是如此。实际上 HashMap 是一个**“链表散列”**。

HashMap 是基于 hashing 的原理。

HashMap 图解

• 我们使用 #put(key, value) 方法来存储对象到 HashMap 中，使用 get(key) 方法从 HashMap 中获取对象。
• 当我们给 #put(key, value) 方法传递键和值时，我们先对键调用 #hashCode() 方法，返回的 hashCode 用于找到 bucket 位置来储存 Entry 对象。

• HashMap的寻址方式

• 对于新插入的数据或者待读取的数据，HashMap将Key的哈希值对数组长度取模，结果作为该Entry在数组中的index。因此数组的长度必须是2的N次方，实际中，HashMap会自动通过Integer.highestOneBit算出比指定整数大的最小的N值。

• public static int highestOneBit(int i) {

  i |= (i >> 1);

  i |= (i >> 2);

  i |= (i >> 4);

  i |= (i >> 8);

  i |= (i >> 16);

  return i - (i >>> 1);

  }

• 碰撞：由于数组的长度是有限的，所以不管Hash（）方法和Equals()方法写得如何严谨，始终不能完全避免碰撞的发生（Hash值算出来的Index相同，需要放在数组的同一个位置），碰撞发生后，我们就只能添加一个链表子节点，但是这无疑会降低查找效率（找到Index还要遍历链表。。。）
• 加载因子：默认是0.75，当数组的被占空间>=0.75的时候，HashMap就会进行扩容（变为两倍），扩容之后数组中的所有元素进行重排序（算出来的Index可能不同），从而减少数组下链表的长度，提高查找效率。
• Java8 中的HashMap采用了数组+链表+红黑树（类似于数据结构中的平衡二叉树）的模式（当链表长度8时由链表的数据结构转换成红黑树的数据结构）
• 在JDK1.8中采用了尾插法，可以有效避免上述这种死循环的情况

? 当两个对象的 hashCode 相同会发生什么？

因为 hashcode 相同，所以它们的 bucket 位置相同，“碰撞”会发生。

因为 HashMap 使用链表存储对象，这个 Entry（包含有键值对的 Map.Entry 对象）会存储在链表中。

? hashCode 和 equals 方法有何重要性？

HashMap 使用 key 对象的 #hashCode() 和 #equals(Object obj) 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候，这些方法也会被用到。

• 如果这两个方法没有被正确地实现，在这种情况下，两个不同 Key 也许会产生相同的 #hashCode() 和 #equals(Object obj) 输出，HashMap 将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。

同样的，所有不允许存储重复数据的集合类都使用 #hashCode() 和 #equals(Object obj) 去查找重复，所以正确实现它们非常重要。#hashCode() 和 #equals(Object obj) 方法的实现，应该遵循以下规则：

• 如果 o1.equals(o2) ，那么 o1.hashCode() == o2.hashCode() 总是为 true 的。
• 如果 o1.hashCode() == o2.hashCode() ，并不意味 o1.equals(o2) 会为 true 。

? HashMap 默认容量是多少？

默认容量都是 16 ，负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容，最小的可能性是（16 * 0.75 = 12），一般为原内存的 2 倍。

? 有哪些顺序的 HashMap 实现类？

• LinkedHashMap ，是基于元素进入集合的顺序或者被访问的先后顺序排序。【基本和HashMap实现类似，多了一个链表来维护元素插入的顺序，因此维护的效率会比HashMap略低。但是因为有链表的存在，遍历效率会高于HashMap。】
• TreeMap ，是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

? 我们能否使用任何类作为 Map 的 key？

我们可以使用任何类作为 Map 的 key ，然而在使用它们之前，需要考虑以下几点：

• 1、如果类重写了 equals 方法，它也应该重写 hashcode 方法。
• 2、类的所有实例需要遵循与 equals 和 hashcode 相关的规则。
• 3、如果一个类没有使用 equals ，你不应该在 hashcode 中使用它。
• 4、用户自定义 key 类的最佳实践是使之为不可变的，这样，hashcode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保hashcode 和 equals 在未来不会改变，这样就会解决与可变相关的问题了。

比如，我有一个 类MyKey ，在 HashMap 中使用它。代码如下：

//传递给MyKey的name参数被用于equals()和hashCode()中 MyKey key = new MyKey('Pankaj'); //assume hashCode=1234 myHashMap.put(key, 'Value'); // 以下的代码会改变key的hashCode()和equals()值 key.setName('Amit'); //assume new hashCode=7890 //下面会返回null，因为HashMap会尝试查找存储同样索引的key，而key已被改变了，匹配失败，返回null myHashMap.get(new MyKey('Pankaj'));

? HashMap 的长度为什么是 2 的幂次方？

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：

• 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方；）。
• 并且，采用二进制位操作 &，相对于 % 能够提高运算效率，

这就解释了 HashMap 的长度为什么是 2 的幂次方。

HashSet 的工作原理是什么？

HashSet 是构建在 HashMap 之上的 Set hashing 实现类。让我们直接撸下源码，代码如下：

// HashSet.java private transient HashMap map; private static final Object PRESENT = new Object();

• 1
• 2
• 3
• 4
• 5
• 6

• map 属性，当我们创建一个 HashMap 对象时，其内部也会创建一个 map 对象。后续 HashSet 所有的操作，实际都是基于这个 map 之上的封装。
• PRESENT 静态属性，所有 map 中 KEY 对应的值，都是它，避免重复创建。
• OK ，再来看一眼 add 方法，代码如下：

// HashSet.java public boolean add(E e) { return map.put(e, PRESENT) == null; }

• • 1
  • 2
  • 3
  • 4
  • 5
  • 6

• • 是不是一目了然。

? HashSet 如何检查重复？

正如我们上面看到 HashSet 的实现原理，我们自然可以推导出，HashMap 也是如何检查重复滴。

如下摘取自 《Head First Java》 第二版：

当你把对象加入 HashSet 时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较。

• 如果没有相符的 hashcode ，HashSet会假设对象没有重复出现。
• 但是如果发现有相同 hashcode 值的对象，这时会调用 equals 方法来检查 hashcode 相等的对象是否真的相同。

• • 如果两者相同，HashSet 就不会让加入操作成功。
  • 如果两者不同，HashSet 就会让加入操作成功。