## 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/raw/master/notes/JavaArchitecture/assets/hashtable1.png)](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/raw/master/notes/JavaArchitecture/assets/hashtable2.png)](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/raw/master/notes/JavaArchitecture/assets/hashtable3.png)](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/raw/master/notes/JavaArchitecture/assets/hash-to-badlink.png)](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