HashMap 简介
1.Hash Map
Hash Map 是一个散列表,这个散列表是无序的,存储的数据是以键值对的形式存储,一个key,对应一个value。
{
"user_name":"tom",
"user_sexy":"man",
"user_age":"18"
}
2.哈希表的映射
百度百科这么定义,散列表,是通过把key映射到表中的某一个位置,地址空间内就是value值。这个映射函数叫散列函数,存放记录的数组叫散列表。
address = f(key) //"映射函数"
也就是说我们认知的hash map 的 key 对 value 实际上是key 对应一个唯一地址,这个地址存放着这个value
3.哈希冲突
同样因为映射的缘故,存在这么一种情况
f(key1)= f(key2)
两个不同的key值指向了同一个address,这个就是哈希冲突
HashMap 对于这种冲突的解决方式采用了 数组+链表+红黑树的方式。
源码如下:
/**
* 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;
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
...
}
有冲突就以链表的形式(next 不为null),没有冲突就是一个数组形式 (next 为null)
4.效率问题
再从上面也可以看出一个问题,因为数据存储的方式不仅限于数组,所以当发生哈希冲突的时候,查询效率和不发生冲突有比较大的区别,一个在于next不为null时需要遍历一遍链表,而为null时不需要遍历,仅需要根据hashcode查一遍node数组就好了,红黑树他们说也有利于提升效率,具体怎样等我研究下。
网友评论