知识问题(持续更新中)"/>
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
循环:for foreatch Iterator迭代器
获取:get(index)、poll()、peek()
3.2、Set
循环:foreatch Iterator迭代器
3.3、Map
循环:foreatch entrySet() keySet()
获取:get(key)
4、Array和ArrayList区别
4.1、空间
Array指定空间大小,不可扩展
ArrayList动态空间,0.5倍扩展,newCapacity=oldCapacity+(oldCapacity>>1)
4.2、存储数据
Array存储基础类型和对象类型
ArrayList只存储对象类型
4.5、方法
Array没有删除方法
ArrayList删除remove方法
更多推荐
Java 知识问题(持续更新中)
发布评论