Java关于HashMap的总结

Map集合 存储键值对，不能有重复的key，每一个key对应一个value；

哈希表

散列表，是根据关键码值（key）进行访问的数据结构，也就是说，通过将key映射到表中一个位置来获取记录，加快查找的速度，这个映射函数叫做散列函数，存放记录的结构称之为散列表；寻址容易，插入删除也容易的数据结构；
链表的时间复杂度为O（N），二叉排序树的时间复杂度为O（log2 N）
散列表可以根据key来找到value，时间复杂度达到O（1）
key采用hash函数来定位，通过hash函数可以得到散列码值；
通常以下几种方式构造哈希函数
（1）直接定址法：key address（key） = a*key+b；
（2）平方取中法：给key值平方，取中间两位作为哈希函数的散了码
（3）折叠法：把key拆分为几部分，例如图书馆里的书，拆分为区域号-书架号-图书编号，这几个号码做一些运算作为散列码
（4）除留取余法：key作为被除数，hash表对应的最大长度m，取不大于m的质数作为除数，key%质数作为散列码；

哈希冲突

如果哈希函数构造的不好，容易产生哈希冲突，使得时间复杂度从O（1）升为O（N）或更大。

解决哈希冲突：

（1）开放地址法：当插入元素且得到两个散列码相同时，第一个元素插入后，第二个元素插入到它后面的位置。
（2）链地址法：当插入元素且得到两个元素散列码相同时，第一个元素插入后，在这个元素的位置加入一个链表，插入第二个元素；hashmap采用链地址法解决hash冲突。

HashMap的使用

hashmap是基于哈希表非同步实现的，哈希表对应的接口是Map接口（非线程安全），我们可以通过key和hash函数得到散列码，从而定位位置，进行增删改查的操作。
jdk1.8之前，HashMap都是采用数组+链表实现的，即使用链地址法处理哈希冲突；不同的key值可能得到同样的散列码，同一Hash值的节点都存储在一个链表中，但是当链表中的元素越来越多的时候；通过key去查找的效率反而从O（1）~O（N）。jkd1.8中，HashMap采用数组+链表+红黑树的结构实现，当前链表的长度超过阈值8，将链表转换为红黑树，红黑树中的元素个数小于6，将红黑树再转换为链表。

自定义HashMap

hash算法直接使用源码中的hash算法，解决哈希冲突采用链地址法，即数组+链表实现，包括方法有put（K key，V value），get（K key），remove（K key）等方法
HashMap迭代器实现
（1）哈希表中数据分布是不连续的，在迭代器初始化的过程中必须先跳转到第一个非空数据节点
（2）当迭代器的下标到达当前桶的链表末尾时，迭代器下标跳转到下一个非空桶的第一个数据节点

class MyHashMap<K,V>{
private Node<K, V>[] table;
private int size;
class Node<K,V>{
protected K key;
protected V value;
protected int hash;
protected Node<K, V> next;
public Node(K key, V value, int hash) {
this.key = key;
this.value = value;
this.hash = hash;
}
}
public MyHashMap(int capacity){
table = new Node[capacity];
}
public Iterator<Node<K, V>> iterator(){
return new Itr();
}
class Itr implements Iterator<Node<K, V>>{
private int currentIndex;//当前桶的位置
private Node<K, V> nextNode;//返回的下一个数据节点
private Node<K, V> currentNode; //上一次next返回的数据节点
public Itr(){
if(MyHashMap.this.isEmpty()){
return;
}
for(int i=0; i < table.length; i++){
currentIndex = i;
Node<K, V> firstNode = table[i];
if(firstNode != null){
nextNode = firstNode;
return;
}
}
}
@Override
public boolean hasNext() {
return nextNode != null;
}
@Override
public Node<K, V> next() {
//返回下一个数据节点
currentNode = nextNode;
//nextNode指向自己的next
nextNode = nextNode.next;
if(nextNode == null){
//说明当前桶的链表已经遍历完毕
//寻找下一个非空的桶
for(int i=currentIndex+1; i<MyHashMap.this.table.length; i++){
//设置当前桶位置
currentIndex = i;
Node<K,V> firstNode = MyHashMap.this.table[currentIndex];
if(firstNode != null){
nextNode = firstNode;
break;
}
}
//nextNode保存的就是下一个非空的数据节点
}
return currentNode;
}
@Override
public void remove() {
if(currentNode == null){
return;
}
K currentKey = currentNode.key;
MyHashMap.this.remove(currentKey);
currentNode = null;
}
}
public void resize(){
//扩容桶table
Node<K, V>[] newTable = new Node[table.length * 2];
for(int i=0; i<table.length; i++){
//将oldTable中每一个位置映射到newTable中
rehash(i, newTable);
}
this.table = newTable;
}
public void rehash(int index, Node<K,V>[] newTable){
Node<K, V> currentNode = table[index];
if(currentNode == null){
return;
}
Node<K, V> lowListHead = null; //低位的头
Node<K, V> lowListTail = null; //低位的尾
Node<K, V> highListHead = null; //高位的头
Node<K, V> highListTail = null; //高位的尾
//currentNode表示oleTable下index位置中当前节点
while(currentNode != null){
//当前节点在newTable中的位置
int newIndex = newTable.length-1 & hash(currentNode.key);
if(newIndex == index){
//映射到原先下标处
if(lowListHead == null){
lowListHead = currentNode;
lowListTail = currentNode;
}else{
lowListTail.next = currentNode;
lowListTail = lowListTail.next;
}
}else{
//newIndex与index不等，映射到高位下标处
if(highListHead == null){
highListHead = currentNode;
highListTail = currentNode;
}else{
highListTail.next = currentNode;
highListTail = lowListTail.next;
}
}
currentNode = currentNode.next;
}
//将lowList head->tail之前的节点链接到index位置
if(lowListTail != null){
newTable[index] = lowListHead;
lowListHead.next = null;
}
//将highList head->tail之前的节点链接到index+table.length位置
if(highListTail != null){
newTable[index+this.table.length] = highListHead;
highListHead.next = null;
}
}
public int hash(Object key) {
int h;
return (h = key.hashCode()) ^ (h >>> 16);
}
public void put(K key, V value){
//确定所要添加元素的位置
int hash = hash(key);//散列码
int index = table.length-1 & hash;//确定的位置
//newNode -》table[index] == null || key在map不存在
//table[index]已经存在数据
//table[index]不存在数据
Node<K, V> firstNode = table[index];//得到该位置的第一个节点
if(firstNode == null){
table[index] = new Node(key, value, hash);
size++;
}else{
//第一种情况 key已经存在 考虑新值覆盖旧值
//第二种情况 key不存在
封装一个新的node尾插法插入链表
if(firstNode.key.equals(key)){
firstNode.value = value; //新值替换旧值
}else{
Node<K,V> tmp = firstNode;
while(tmp.next != null && !tmp.key.equals(key)){
tmp = tmp.next;
}
if(tmp.next == null){
if(tmp.key.equals(key)){
tmp.value = value; //新值替换旧值
}else{
tmp.next = new Node(key, value, hash);
size++;
}
}else{
tmp.value = value;
}
}
}
}
public boolean remove(K key){
int hash = hash(key);
int index = table.length-1 & hash;
Node<K, V> firstNode = table[index];
if(firstNode == null){
return false;
}else{
if(firstNode.next == null){
if(firstNode.key.equals(key) && firstNode.hash == hash){
//为什么判断key是否相等的同时还需要判断散列码
table[index] = null;
return true;
}
}
Node<K,V> tmpPrev = firstNode;
Node<K, V> tmp = firstNode.next;
while(tmp.next != null){
if(tmp.key.equals(key) && tmp.hash == hash){
//tmp之前节点的next指向tmp.next
tmpPrev.next = tmp.next;
size--;
}else{
tmpPrev = tmp;
tmp = tmp.next;
}
}
}
return false;
}
public Node<K,V> get(K key){
//获取对应key所在数组的index
int hash = hash(key);//散列码
int index = table.length - 1 & hash; //定位key记录所在的位置
Node<K, V> firstNode = table[index];
if (firstNode == null) {
return null;
}
if (hash == firstNode.hash && key == firstNode.key) {
return firstNode;
} else {
//遍历链表
Node<K, V> currentNode = firstNode.next;
while (currentNode != null) {
if (currentNode.hash == hash && currentNode.key == key) {
return currentNode;
}
currentNode = currentNode.next;
}
}
return null;
}
public boolean isEmpty(){
return size == 0;
}
}
public class TestDemo11 {
public static void main(String[] args) {
}
}

源码

以putvalue为例

 * static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
16
* static final int MAXIMUM_CAPACITY = 1 << 30;
* static final float DEFAULT_LOAD_FACTOR = 0.75f;
* static final int TREEIFY_THRESHOLD = 8; 桶上的节点个数大于8时会转为红黑树
* static final int UNTREEIFY_THRESHOLD = 6; 桶上的绩点个数小于6时会转为链表
* static final int MIN_TREEIFY_CAPACITY = 64; 桶中结构转化为红黑树对用的table的最小大小
* transient Node<K,V>[] table; 存储元素的数组 总是2的幂次方
* transient Set<Map.Entry<K,V>> entrySet;
哈希表中节点的集合
* transient int size;
* transient int modCount;
* int threshold; 临界值
* final float loadFactor;
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;
if ((p = tab[i = (n - 1) & 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 1st
treeifyBin(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 key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

HashMap和HashTabl的区别

weakHashMap是特殊HashMap
WeakHashMap的键关联的对象是弱引用对象

static class Entyr<K,V>extends WeakReference<Object>Entry 继承自WeakHashMap

Java中四种引用
1.强引用
通过new出来对象所关联的引用称之为强引用，只要强引用存在，当前对象不会被回收
2.软引用
通过SoftReference类实现，在系统内存即将要溢出的时候，才会回收软引用对象
3.弱引用
通过WeakReference实现，只要发生垃圾回收，被弱引用关联的对象就会被回收掉
4.虚引用
通过PhantomReference实现，无法通过虚引用获取对象实例，唯一作用就是在这个对象被回收时，能够收到一个通知

最后

以上就是还单身自行车为你收集整理的Java关于HashMap的总结自定义HashMap的全部内容，希望文章能够帮你解决Java关于HashMap的总结自定义HashMap所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。