## 1\. ArrayList和LinkedList区别 * ArrayList 和 LinkedList 可想从名字分析，它们一个是 Array (动态数组) 的数据结构，一个是 Link (链表) 的数据结构，此外，它们两个都是对 List 接口的实现。前者是数组队列，相当于动态数组；后者为双向链表结构，也可当作堆栈、队列、双端队列； * **当随机访问 List 时**（get和set操作），ArrayList 比 LinkedList的效率更高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找； * **当对数据进行增加和删除的操作时**（add 和 remove 操作），LinkedList 比 ArrayList 的效率更高，因为 ArrayList 是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动； * **从利用效率来看**，ArrayList 自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而 LinkedList 自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用； * ArrayList 主要空间开销在于需要在 List 列表预留一定空间；而 LinkList 主要控件开销在于需要存储结点信息以及结点指针信息。 * **ArrayList、LinkedList 和 Vector如何选择？** * 当对数据的主要操作为索引或只在集合的末端增加、删除元素时，使用 ArrayList 或 Vector 效率比较高； * 当对数据的操作主要为制定位置的插入或删除操作时，使用 LinkedList 效率比较高； * 当在多线程中使用容器时（即多个线程会同时访问该容器），选用 Vector 较为安全； ## 2\. HashMap和HashTable区别，HashMap的key类型 * **Hash Map和HashTable的区别** * Hashtable 的方法是同步的，HashMap 非同步，所以在多线程场合要手动同步 * Hashtable 不允许 null 值 (key 和 value 都不可以)，HashMap 允许 null 值( key 和 value 都可以)。 * 两者的遍历方式大同小异，Hashtable 仅仅比 HashMap 多一个 elements 方法。 * Hashtable 和 HashMap 都能通过 values() 方法返回一个 Collection ，然后进行遍历处理。 * 两者也都可以通过 entrySet() 方法返回一个 Set ， 然后进行遍历处理。 * HashTable 使用 Enumeration，HashMap 使用 Iterator。 * 哈希值的使用不同，Hashtable 直接使用对象的 hashCode。而 HashMap 重新计算hash值，而且用于代替求模。 * Hashtable 中 hash 数组默认大小是11，增加的方式是 old\*2+1。HashMap 中 hash 数组的默认大小是16，而且一定是 2 的指数。 * HashTable 基于 Dictionary 类，而 HashMap 基于 AbstractMap 类 * **HashMap中的key可以是任何对象或数据类型吗** * 可以为null，但不能是可变对象，如果是可变对象的话，对象中的属性改变，则对象 HashCode 也进行相应的改变，导致下次无法查找到已存在Map中的数据。 * 如果可变对象在 HashMap 中被用作键，那就要小心在改变对象状态的时候，不要改变它的哈希值了。我们只需要保证成员变量的改变能保证该对象的哈希值不变即可。 * **HashTable是线程安全的么** * HashTable 是线程安全的，其实现是在对应的方法上添加了 synchronized 关键字进行修饰，由于在执行此方法的时候需要获得对象锁，则执行起来比较慢。所以现在如果为了保证线程安全的话，使用 CurrentHashMap。 ## 3\. HashMap和ConcurrentHashMap * **HashMap和Concurrent HashMap区别？** * HashMa p是非线程安全的，CurrentHashMap 是线程安全的。 * ConcurrentHashMap 将整个 Hash 桶进行了分段 segment，也就是将这个大的数组分成了几个小的片段segment，而且每个小的片段 segment 上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段 segment，然后再在这个片段上面进行插入，而且这里还需要获取 segment 锁。 * ConcurrentHashMap 让锁的粒度更精细一些，并发性能更好。 * **ConcurrentHashMap 线程安全吗， ConcurrentHashMap如何保证 线程安全？** * HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问 HashTable 的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是 ConcurrentHashMap 所使用的**分段锁**，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。 * get 操作的高效之处在于整个 get 过程不需要加锁，除非读到的值是空的才会加锁重读。**get 方法里将要使用的共享变量都定义成 volatile**，如用于统计当前 Segement 大小的 count 字段和用于存储值的 HashEntry 的 value。定义成 volatile 的变量，能够在线程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写（有一种情况可以被多线程写，就是写入的值不依赖于原值），在 get 操作里只需要读不需要写共享变量 count 和 value，所以可以不用加锁。 * put 方法首先定位到 Segment，然后在 Segment 里进行插入操作。 * 插入操作需要经历两个步骤：（1）判断是否需要对 Segment 里的 HashEntry 数组进行扩容；（2）定位添加元素的位置然后放在HashEntry数组里。 ## 4\. Hashtable的原理 **Hashtable 使用链地址法进行元素存储，通过一个实际的例子来演示一下插入元素的过程：** 假设我们现在 Hashtable 的容量为 5，已经存在了 (5,5)，(13,13)，(16,16)，(17,17)，(21,21) 这 5 个键值对，目前他们在 Hashtable 中的位置如下： [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hashtable1.png) 现在，我们插入一个新的键值对，put(16,22)，假设 key=16 的索引为 1.但现在索引 1 的位置有两个 Entry 了，所以程序会对链表进行迭代。迭代的过程中，发现其中有一个 Entry 的 key 和我们要插入的键值对的 key 相同，所以现在会做的工作就是将 newValue=22 替换 oldValue=16，然后返回 oldValue = 16. [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hashtable2.png) 然后我们现在再插入一个，put(33,33)，key=33 的索引为 3，并且在链表中也不存在 key=33 的 Entry，所以将该节点插入链表的第一个位置。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hashtable3.png) **Hashtable 与 HashMap 的简单比较** 1. HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。 2. HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理，而对 value 没有处理；Hashtable遇到 null，直接返回 NullPointerException。 3. **Hashtable 方法是同步，而HashMap则不是**。我们可以看一下源码，Hashtable 中的几乎所有的 public 的方法都是 synchronized 的，而有些方法也是在内部通过 synchronized 代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用 HashTable，没有涉及就采用 HashMap，但是在 Collections 类中存在一个静态方法：**synchronizedMap()**，该方法创建了一个线程安全的 Map 对象，并把它作为一个封装的对象来返回。 **参考资料：** * [Hashtable 的实现原理 - Java 集合学习指南 - 极客学院Wiki](http://wiki.jikexueyuan.com/project/java-collection/hashtable.html) ## 5\. Hash冲突的解决办法 * 链地址法 * 开放地址法（向后一位） * 线性探测 * 平方探测 * 二次哈希 * 再哈希法 ## 6\. 什么是迭代器 　　Java 集合框架的集合类，我们有时候称之为容器。容器的种类有很多种，比如 ArrayList、LinkedList、HashSet...，每种容器都有自己的特点，ArrayList 底层维护的是一个数组；LinkedList 是链表结构的；HashSet 依赖的是哈希表，每种容器都有自己特有的数据结构。 　　因为容器的内部结构不同，很多时候可能不知道该怎样去遍历一个容器中的元素。所以为了使对容器内元素的操作更为简单，Java 引入了迭代器模式！ 　　把访问逻辑从不同类型的集合类中抽取出来，从而避免向外部暴露集合的内部结构。 　　**迭代器模式**：就是提供一种方法对一个容器对象中的各个元素进行访问，而又不暴露该对象容器的内部细。 ~~~java public static void main(String[] args) { // 使用迭代器遍历ArrayList集合 Iterator<String> listIt = list.iterator(); while(listIt.hasNext()){ System.out.println(listIt.hasNext()); } // 使用迭代器遍历Set集合 Iterator<String> setIt = set.iterator(); while(setIt.hasNext()){ System.out.println(listIt.hasNext()); } // 使用迭代器遍历LinkedList集合 Iterator<String> linkIt = linkList.iterator(); while(linkIt.hasNext()){ System.out.println(listIt.hasNext()); } } ~~~ 参考资料： * [深入理解Java中的迭代器 - Mr·Dragon - 博客园](https://www.cnblogs.com/zyuze/p/7726582.html) ## 7\. 构造相同hash的字符串进行攻击，这种情况应该怎么处理？JDK7如何处理 **攻击原理：** 　　当客户端发送一个请求到服务器，如果该请求中带有参数，服务器端会将 参数名-参数值 作为 key-value 保存在 HashMap 中。如果有人恶意构造请求，在请求中加入大量相同 hash 值的 String 参数名（key），那么在服务器端用于存储这些 key-value 对的 HashMap 会被强行退化成链表，如图： [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/hash-to-badlink.png) 如果数据量足够大，那么在查找，插入时会占用大量 CPU，达到拒绝服务攻击的目的。 **怎么处理** 1. 限制 POST 和 GET 请求的参数个数 2. 限制 POST 请求的请求体大小 3. Web Application FireWall（WAF） **JDK7如何处理** HashMap 会动态的使用一个专门 TreeMap 实现来替换掉它。 ## 8\. Hashmap为什么大小是2的幂次 首先来看一下 hashmap 的 put 方法的源码 ~~~java public V put(K key, V value) { if (key == null) return putForNullKey(value); //将空key的Entry加入到table[0]中 int hash = hash(key.hashCode()); //计算key.hashcode()的hash值，hash函数由hashmap自己实现 int i = indexFor(hash, table.length); //获取将要存放的数组下标 /* * for中的代码用于：当hash值相同且key相同的情况下，使用新值覆盖旧值（其实就是修改功能） */ //注意：for循环在第一次执行时就会先判断条件 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; //hash值相同且key相同的情况下，使用新值覆盖旧值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; //e.recordAccess(this); return oldValue;//返回旧值 } } modCount++; addEntry(hash, key, value, i);//增加一个新的Entry到table[i] return null;//如果没有与传入的key相等的Entry，就返回null } ~~~ ~~~java /** * "按位与"来获取数组下标 */ static int indexFor(int h, int length) { return h & (length - 1); } ~~~ **hashmap 始终将自己的桶保持在2n，这是为什么？indexFor这个方法解释了这个问题** 大家都知道计算机里面位运算是基本运算，位运算的效率是远远高于取余 % 运算的 举个例子：2n转换成二进制就是 1+n 个 0，减 1 之后就是 0+n个1，如16 -> 10000，15 -> 01111 那么根据 & 位运算的规则，都为 1 (真)时，才为 1，那 0≤运算后的结果≤15，假设 h 15，运算后的结果就是最后四位二进制做 & 运算后的值，最终，就是 % 运算后的余数。 当容量一定是 2n时，h & (length - 1) == h % length