Java 知识点总结之Java 基本API（一）

ゝ一纸荒年。 2022-05-28 04:17 125阅读 0赞

**1、String,StringBuffer, StringBuilder 的区别是什么？String为什么是不可变的？**

答：（1）String是字符串常量，StringBuffer和StringBuilder都是字符串变量。后两者的字符内容可变，而前者创建后内容不可变。

（2）String不可变是因为在JDK中String类被声明为一个final类。

（3）StringBuffer是线程安全的，而StringBuilder是非线程安全的。

补充：String类是final的，而且使用private final char value\[\];保存字符串内容

### 2、Vector, ArrayList, LinkedList的区别是什么？ ###

答：（1）Vector、ArrayList都是以类似数组的形式存储在内存中，LinkedList则以链表的形式进行存储。

（2）List中的元素有序、允许有重复的元素，Set中的元素无序、不允许有重复元素。

（3）Vector线程同步，ArrayList、LinkedList线程不同步。

（4）LinkedList适合指定位置插入、删除操作，不适合查找；ArrayList、Vector适合查找，不适合指定位置的插入、删除操作。

（5）ArrayList在元素填满容器时会自动扩充容器大小的50%，而Vector则是100%，因此ArrayList更节省空间。（Vector可以传入增长大小，ArrayList没有增长大小）

补充：Vector是JDK1.0的api，所有方法都是synchronize方法，效率非常低。

Stack也是JDK1.0的API，继承Vector。

Vector和Stack被弃用

高并发下，使用java.util.concurrent.CopyOnWriteArrayList等替代Vector

使用java.util.concurrent.ConcurrentLinkedDeque或者java.util.concurrent.ConcurrentLinkedQueue替代Stack

### 3、HashTable, HashMap，TreeMap区别？ ###

答：（1）HashTable线程同步，HashMap、TreeMap非线程同步。

（2）HashTable不允许<键,值>有空值，HashMap允许<键,值>有空值。

（3）HashTable使用Enumeration，继承Dictionary类，实现Map接口；HashMap使用Iterator，实现Map接口；TreeMap实现SortedMap接口

（4）HashTable中hash数组的默认大小是11，增加方式的old\*2+1，HashMap中hash数组的默认大小是16，增长方式一定是2的指数倍。

（5）TreeMap能够把它保存的记录根据键排序，默认是按升序排序。

（6）TreeMap采用红黑树（平衡二叉树）

补充：HashTable是JDK1.0的api，所有方法都是synchronize方法，效率非常低。可以用ConcurrentHashMap替代。但是并不能完全被取代，两者的迭代器的一致性不同的，hash table的迭代器是强一致性的，而concurrenthashmap是弱一致的。 ConcurrentHashMap的get，clear，iterator 都是弱一致性的。 Doug Lea 也将这个判断留给用户自己决定是否使用ConcurrentHashMap。

FastTreeMap是apache commons的api，有fast、slow模式，都是线程安全的

Fast模式下，写是复制对象，用synchronize， 读是从旧对象中读取

CopyOnWriteArrayList，set是复制对象，用ReentrantLock， 读是从旧对象中读取

### 4、Enumeration、Iterator、Iteratable区别？ ###

答：（1）Iterator替代Enumeration，

（2）Iterator方法：boolean hasNext()，Object next()，void remove()

Enumeration方法：booleanhashMoreElements()，Object nextElement()

（2）Enumeration中没有删除方法，只有遍历。

（3）Enumeration是先进后出，而Iterator是先进先出。

（4）Iterator是迭代器，有boolean hasNext()，Object next()，void remove()

Iteratable是接口，有Iterator<T>iterator();

比如ArrayList实现Iteratable接口，iterator()方法返回的是Iterator迭代器实现

补充：使用了Iteratable接口，可以使用foreach方法

### 5、JDK7.0下HashMap的内部实现机制，hash是怎么实现的，什么时候rehash ###

答：（1）HashMap内部是Entry数组（Hash表）， Entry是一个单向链表。HashMap的内部实现结合了链表和数组的优势

![70][]

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

（2）源码分析，请参考：https://www.cnblogs.com/chengxiao/p/6059914.html

默认值initialCapacity默认为16，loadFactory默认为0.75

public V put(K key, V value) {
    
           //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
    
           if (table == EMPTY_TABLE) {
    
               inflateTable(threshold);
    
           }
    
          //如果key为null，存储位置为table[0]或table[0]的冲突链上
    
           if (key == null)
    
               return putForNullKey(value);
    
           int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
    
           int i = indexFor(hash, table.length);//获取在table中的实际位置
    
           for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    
           //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
    
               Object k;
    
               if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    
                    V oldValue = e.value;
    
                    e.value = value;
    
                    e.recordAccess(this);
    
                    return oldValue;
    
               }
    
           }
    
           modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
    
           addEntry(hash, key, value, i);//新增一个entry
    
           return null;
    
    }

在扩容的过程中需要进行ReHash操作，而这是非常耗时的，在实际中应该尽量避免。

（3）当size达到阈值时，需要进行数组扩容rehash，数组长度一定是2的次幂，因为是：为了hash的平均分布。如果不是2的次幂，会导致部分位置会永远分配不到。

（4）hash算法：直接定址法、求余法、数字分析法、平方取中法、折叠法、随机数法等。为了减少冲突

（5）如果两个键的hashcode相同，如何获取值对象?

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。

（6）重新调整HashMap大小存在什么问题吗？

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

补充：关于HashMap其他几个问题

（1）      为什么String, Interger这样的wrapper类适合作为键？

String, Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

（2）      可以使用自定义的对象作为键吗？

使用任何对象作为键，只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。定义为final类

（3）      可以使用CocurrentHashMap来代替Hashtable吗？

Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性

### 6、JDK8.0下HashMap的内部实现机制，hash是怎么实现的，什么时候rehash ###

答：（1）Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。JDK8优化高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)

（2）链表长度大于8，转换为红黑树

（3）rehash，不需要重新计算hash值，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。

（4）JDK1.8引入红黑树大程度优化了HashMap的性能。

[70]: /images/20220528/d6dc1f550da84ea2a3356160b245a96c.png