Java 知识问题（持续更新中）

编程入门行业动态更新时间:2024-10-26 06:33:50

Java <a href=https://www.elefans.com/category/jswz/34/1769308.html style= 知识问题（持续更新中）"/>

Java 知识问题（持续更新中）

一、集合问题

1、问题：ArrayList,Vector, LinkedList 区别

1）、数据结构不同：ArrayList和Vector采用动态数组（ArrayList默认10扩容0.5，Vector默认扩容1倍），LinkedList采用链表方式

2）、线程安全：Vector类方法带有synchronized关键字保证线程安全，性能比ArrayList差

3）、性能比较：LinkedList 增删改快，ArrayList查询快，Vector线程安全较慢

4）、选择：单线程使用ArrayList和LinkedList，多线程建议使用Collections工具类，vector官方已不建议使用，属于Java中的遗留容器（遗留容器还有Hashtable、Dictionary、BitSet、Stack、Properties）

2、快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别？【这里用iterator举例，其他还有hashmap等不一一举例说明】

引用：

1)、fail-fast：通过抛出ConcurrentModificationException异常来触发的

2)、fail-safe：没有抛出ConcurrentModificationException异常：

当多个线程对Collection进行操作时，一个线程通过iterator去遍历集合时，该集合的内容被其他线程所改变，则会抛出ConcurrentModificationException异常。

fast-fail解决办法：通过util.concurrent集合包下的相应类去处理。new ArrayList<String>()替换成new CopyOnWriteArrayList<String>()。因为ArrayList继承AbstractList，当调用 next() 和 remove()时，都会执行 checkForComodification()

        final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}

延伸：ArrayList和CopyOnWriteArrayList的区别

        (1) 和ArrayList继承于AbstractList不同，CopyOnWriteArrayList没有继承于AbstractList，它仅仅只是实现了List接口。
        (2) ArrayList的iterator()函数返回的Iterator是在AbstractList中实现的；而CopyOnWriteArrayList是自己实现Iterator。
        (3) ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常！

3、hashmap数据结构、工作原理、扩容机制

1)、数据结构

采用Entry数组来存储key-value对（数组默认大小为16），每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，依次来解决Hash冲突的问题，因为HashMap是按照Key的hash值来计算Entry在HashMap中存储的位置的，如果hash值相同，而key内容不相等，那么就用链表来解决这种hash冲突。

Entry数组：hashmap主体组成单元，包含一个key-value键值对和next指针

private static class Entry<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Entry<K,V> next;protected Entry(int hash, K key, V value, Entry<K,V> next) {this.hash = hash;this.key =  key;this.value = value;this.next = next;}@SuppressWarnings("unchecked")protected Object clone() {return new Entry<>(hash, key, value,(next==null ? null : (Entry<K,V>) next.clone()));}// Map.Entry Opspublic K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {if (value == null)throw new NullPointerException();V oldValue = this.value;this.value = value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>)o;return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&(value==null ? e.getValue()==null : value.equals(e.getValue()));}public int hashCode() {return hash ^ Objects.hashCode(value);}public String toString() {return key.toString()+"="+value.toString();}}

线性链表：hash冲突链表

二叉树：红黑树

哈希表：根据哈希函数f(key)计算实际存储位置

 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

2）、属性变量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16

static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量

static final float DEFAULT_LOAD_FACTOR = 0.75f;//装载因子默认0.75

static final int TREEIFY_THRESHOLD = 8;//数组容量，链表长度大于8可能转红黑树(元素小于MIN_TREEIFY_CAPACITY 优先扩容)

static final int UNTREEIFY_THRESHOLD = 6;//红黑树节点数小于6，转为链表

static final int MIN_TREEIFY_CAPACITY = 64;//数组容量大于等于64且链表长度大于8就转红黑树

2.1、如果链表的长度大于 8（TREEIFY_THRESHOLD ）会尝试调用 treeifyBin 方法

if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;
}

2.2、如果表的长度小于 64（MIN_TREEIFY_CAPACITY ）会先扩容

    final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}

详细内容：JDK1.8源码中的HashMap_cainiaoblog的博客-CSDN博客

3）、put方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** Implements Map.put and related methods** @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent if true, don't change existing value* @param evict if false, the table is in creation mode.* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0) //是否初始化n = (tab = resize()).length;	//扩容初始化：return (Node<K,V>[])new Node[newCap]if ((p = tab[i = (n - 1) & hash]) == null)	//Ebtry[] hash位置为null直接赋值tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

4）、get方法，通过hash获取对应位置数据，hash冲突通过getTreeNode获取

    public V get(Object key) {Node<K,V> e;return (e = getNode(key)) == null ? null : e.value;}/*** Implements Map.get and related methods.** @param key the key* @return the node, or null if none*/final Node<K,V> getNode(Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & (hash = hash(key))]) != null) {if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);}

5）、remove移除

    public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}/*** Implements Map.remove and related methods.** @param hash hash for key* @param key the key* @param value the value to match if matchValue, else ignored* @param matchValue if true only remove if value is equal* @param movable if false do not move other nodes while removing* @return the node, or null if none*/final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}

hashmap面试问题引用：

3、List Set Map 存取数据区别

1）、结构

List和Set存储单列数据，Map存储键值对数据

List数据有序且允许重复；Set无序（除了TreeSet）且不允许重复；Map无序，键不允许重复，值允许重复

2）、实现

2.1、 List接口

LinkedList：链表，内存是散列的，增删快，查找慢
ArrayList：数组，非线程安全，增删慢，查找快；
Vector：数组，线程安全，增删慢，查找慢；

2.2、Set接口

HashSet：根据元素hashcode存放，底层是散列表（Node[]数组 + 单链表 + 红黑树）

TreeSet：利用红黑树进行排序，底层是二叉树

LinkedHashSet：根据元素hashcode存放，内部维护了一个双向链表

2.3、Map接口

HashMap：根据hashcode存放数据，线程不安全，支持null值和null键

HashTable：根据hashcode存放数据，线程安全，不支持null值和null建

LinkedHashMap: 根据元素hashcode存放，内部维护了一个双向链表(hashMap+linkList)

TreeMap：根据键利用红黑树进行排序，默认是键值的升序排序

3）、取数据

3.1、List