1、HashMap 和 HashTable 有什么区别？
HashMap：
继承AbstractMap<K,V>类，实现了Map<K,V>, Cloneable, Serializable接口
采用数组+链表+红黑树实现（jdk1.8后，采用红黑树）
- 非线程安全
- Key可以为null，但只允许有一个，value可以为null，不限个数
- 默认初始容量为16，每次扩充，容量变为原来的2倍
- hash计算方式：
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); - 数组下标计算方式：
int index = (n - 1) & hash - HashMap使用Iterator进行遍历
Hashtable
继承了Dictionary类，实现了Map<K,V>, Cloneable, java.io.Serializable接口
底层结构是Entry数组
-
几乎所有方法都采用synchronized修饰，线程安全
-
不允许key或者value为null，value为空会直接抛出NPE，Hashtable中key的hash计算方法是直接调用Object中的hashCode()方法，所以key也不能为空
-
默认的初始大小为11，之后每次扩充，容量变为原来的2n+1：
int newCapacity = (oldCapacity << 1) + 1; -
hash计算方法：
key.hashCode() -
数组下标计算方法：
(hash & 0x7FFFFFFF) % tab.length; -
HashTable使用Enumeration遍历
HashMap：
HashMap主要成员变量：
-
transient Node<K,V>[] table：这是一个Node类型的数组（也有称作Hash桶），可以从下面源码中看到静态内部类Node在这边可以看做就是一个节点，多个Node节点构成链表，当链表长度大于8的时候转换为红黑树。
/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K,V>[] table; //哈希桶 -
transient int size：表示当前HashMap包含的键值对数量
-
transient int modCount：表示当前HashMap修改次数
-
int threshold：表示当前HashMap能够承受的最多的键值对数量，一旦超过这个数量HashMap就会进行扩容
-
final float loadFactor：负载因子，用于扩容
-
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4：默认的table初始容量
-
static final float DEFAULT_LOAD_FACTOR = 0.75f：默认的负载因子
-
static final int TREEIFY_THRESHOLD = 8: 链表长度大于等于该参数转红黑树
-
static final int UNTREEIFY_THRESHOLD = 6: 当树的节点数小于等于该参数转成链表
Node节点：
Node是HashMap的一个内部类，实现了Map.Entry接口，本质上是一个映射关系
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//定位数组索引位置
final K key;
V value;
Node<K,V> next;//链表下一个Node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
哈希冲突：
HashMap采用链地址法处理hash冲突，在每个数组元素上都加一个链表结构，当数据被Hash后得到数组下标，把数据放在对应下标元素的链表上。
hash值：
static final int hash(Object key) {
int h;
//第一步 h = key.hashCode() 求hashCode
//第二步 h ^ (h >>> 16) 高位运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap中的put方法：
HashMap中的get方法：
- 对key的hashCode()做hash运算，计算index。
- 如果在bucket⾥的第⼀个节点⾥直接命中，则直接返回。
- 如果有冲突，则通过key.equals(k)去查找对应的Entry
- 若为树，则在树中通过key.equals(k)查找，O(logn)
- 若为链表，则在链表中通过key.equals(k)查找，O(n)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != 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);
}
}
return null;
}
2、数组和链表的区别
ArrayList:
- ArrayList非线程安全，底层是一个Object[]，添加到ArrayList中的数据保存在了elementData属性中。
- 当调用
new ArrayList<>()时，将一个空数组{}赋值给了elementData，这个时候集合的长度size为默认长度0； - 当调用
new ArrayList<>(100)时，根据传入的长度，new一个Object[100]赋值给elementData，当然如果玩儿的话，传了一个0，那么将一个空数组{}赋值给了elementData； - 当调用new ArrayList<>(new HashSet())时，根据源码，我们可知，可以传递任何实现了Collection接口的类，将传递的集合调用toArray()方法转为数组内赋值给elementData;
向ArrayList添加元素：
public boolean add(E e) {//直接添加数据
ensureCapacityInternal(size + 1); //判断Object[]数组是否有足够空间
elementData[size++] = e;//在对应位置添加元素
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);// 判断index 是否有效
ensureCapacityInternal(size + 1); //判断Object[]数组是否有足够空间
System.arraycopy(elementData, index, elementData, index + 1,
size - index);//将index 后面的数据都往后移一位
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {//进行数组扩容
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容规则为“数组当前足够的最小容量 + （数组当前足够的最小容量 / 2）”，即数组当前足够的最小容量 * 1.5，当然有最大值的限制。
在ArrayList中查找元素：
public E get(int index) {
rangeCheck(index);//需要判断传入的数组下标是否越界
return elementData(index);
}
E elementData(int index) {//通过下标查找，同时进行类型转换
return (E) elementData[index];
}
private void rangeCheck(int index) {//判断传入的数组下标是否越界
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
移除ArrayList中元素：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;//计算数组中需要移动的位数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {//遍历底层数组elementData
fastRemove(index);//获取下标，调用remove(int index)
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {//遍历底层数组elementData
fastRemove(index);//获取下标，调用remove(int index)
return true;
}
}
return false;
}
LinkedList：
-
继承于 AbstractSequentialList ，本质上面与继承 AbstractList 没有什么区别，AbstractSequentialList 完善了 AbstractList 中没有实现的方法。
-
Serializable：成员变量 Node 使用 transient 修饰，通过重写read/writeObject 方法实现序列化。
-
Cloneable：重写clone（）方法，通过创建新的LinkedList 对象，遍历拷贝数据进行对象拷贝。
-
Deque：实现了Collection 大家庭中的队列接口，说明他拥有作为双端队列的功能。
-
LinkedList与ArrayList最大的区别就是LinkedList中实现了Collection中的 Queue（Deque）接口 拥有作为双端队列的功能
-
ListedList采用的是链式存储。链式存储就会定一个节点Node。包括三部分前驱节点、后继节点以及data值。所以存储存储的时候他的物理地址不一定是连续的。
LinkedList集合Node结构：
private static class Node<E> {
E item;//值
Node<E> next;//后继节点
Node<E> prev;//前驱节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
定义：
LinkedList实现了Deque（间接实现了Qeque接口），Deque是一个双向对列，为LinedList提供了从对列两端访问元素的方法
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
初始化：
//初始化长度为0
transient int size = 0;
//有前后节点
transient Node<E> first;
transient Node<E> last;
向LinkedList添加元素：
public boolean add(E e) {
linkLast(e);//调用linkLast方法，添加位置是集合最后
return true;
}
void linkLast(E e) {
// 将最后一个元素赋值（引用传递）给节点l final修饰符 修饰的属性赋值之后不能被改变
final Node<E> l = last;
// 调用节点的有参构造方法创建新节点 保存添加的元素
final Node<E> newNode = new Node<>(l, e, null);
//此时新节点是最后一位元素 将新节点赋值给last
last = newNode;
//如果l是null 意味着这是第一次添加元素 那么将first赋值为新节点,这个list只有一个元素存储元素
//开始元素和最后元素均是同一个元素
if (l == null)
first = newNode;
else
//如果不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
l.next = newNode;
//长度+1
size++;
//修改次数+1
modCount++;
}
添加到指定位置：
public void add(int index, E element) {
//下标越界检查
checkPositionIndex(index);
//如果是向最后添加 直接调用linkLast
if (index == size)
linkLast(element);
//反之 调用linkBefore
else
linkBefore(element, node(index));
}
//在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null; 假设断言 succ不为null
//定义一个节点元素保存succ的prev引用 也就是它的前一节点信息
final Node<E> pred = succ.prev;
//创建新节点 节点元素为要插入的元素e prev引用就是pred 也就是插入之前succ的前一个元素 next是succ
final Node<E> newNode = new Node<>(pred, e, succ);
//此时succ的上一个节点是插入的新节点 因此修改节点指向
succ.prev = newNode;
// 如果pred是null 表明这是第一个元素
if (pred == null)
//成员属性first指向新节点
first = newNode;
//反之
else
//节点前元素的next属性指向新节点
pred.next = newNode;
//长度+1
size++;
modCount++;
}
LinkedList列表中，查找元素：
public E get(int index) {
//检查下标元素是否存在 实际上就是检查下标是否越界
checkElementIndex(index);
//如果没有越界就返回对应下标节点的item 也就是对应的元素
return node(index).item;
}
//下标越界检查 如果越界就抛异常
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//指定下标的非空节点
Node<E> node(int index) {
//如果index小于size的二分之一 从前开始查找（向后查找） 反之向前查找
if (index < (size >> 1)) {
Node<E> x = first;
//遍历
for (int i = 0; i < index; i++)
//每一个节点的next都是他的后一个节点引用 遍历的同时x会不断的被赋值为节点的下一个元素
//遍历到index是拿到的就是index对应节点的元素
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
体现了双向链表的优越性，可以从前也可以从后开始遍历
3、用面向对象的方法求出数组中重复 value 的个数
//原始数组
int arr[] = {1,4,1,4,2,5,4,5,8,7,8,77,88,5,4,9,6,2,4,1,5};
//利用hashmap记录每个数字出现的次数
Map<Integer, Integer> map = new HashMap<>();
//循环数组
for (int i : arr) {
//判断当前数字是否已经统计过，如果统计过，取出出现的次数，加1 ，
Integer temp = map.get(i);
int ov = 0;
if(temp != null){
ov = temp.intValue();
}
Integer v = new Integer(ov + 1 );
map.put(i, v );
}
//循环输出
Set<Integer> entry = map.keySet();
for (Integer key : entry) {
System.out.println(key + " 出现了 ： " + map.get(key) + " 次");
}
转载：https://blog.csdn.net/yubo_830/article/details/106397354
查看评论