【Java集合篇】HashMap的get方法是如何实现的?

2024-01-08 23:34:14

在这里插入图片描述


??典型解析


下面是JDK 1.8中HashMap的get方法的简要实现过程:


1 . 首先,需要计算键的哈希值,并通过哈希值计算出在数组中的索引位置


2 . 如果该位置上的元素为空,说明没有找到对应的键值对,直接返回null。


3 . 如果该位置上的元素不为空,遍历该位置上的元素,如果找到了与当前键相等的键值对,那么返回该键值对的值,否则返回null


具体来说,get方法首先计算出给定键的哈希值,然后使用这个哈希值在HashMap的内部数组中找到相应的位置。如果这个位置上有数据(即存在键值对),那么就返回该位置的值;如果这个位置上没有数据,那么就返回null。


看一个HashMap的get方法的简单实现:


public V get(Object key) {  
    // 计算哈希值  
    int hash = hash(key);  
    // 在内部数组中找到相应的位置  
    int index = indexFor(hash, table.length);  
    // 判断该位置是否有数据  
    if (table[index] == null) {  
        return null; // 该位置上没有数据  
    } else if (table[index].key == null) {  
        return table[index].value; // 该位置上的键为null,直接返回值  
    } else if (key.equals(table[index].key)) {  
        return table[index].value; // 找到了键值对,返回值  
    } else {  
        return null; // 没找到键值对,返回null  
    }  
}

代码中,hash方法用于计算给定键的哈希值,indexFor方法用于根据哈希值和内部数组的长度计算出相应的索引。如果找到了键值对,那么就返回该键值对的值;否则返回null。


??拓展知识仓


??如何避免HashMap get方法的哈希重


HashMap 的 get 方法在处理哈希冲突时,采用的是链地址法(Separate Chaining)。具体来说,当两个或更多的键计算出相同的哈希值时,它们会被放在同一个链表中。当 get 方法被调用时,首先计算出键的哈希值,然后在这个链表中查找相应的键。


要避免 HashMap 的 get 方法出现哈希冲突,可以考虑以下几点:


  1. 选择合适的哈希函数

在Java中,HashMap的默认哈希函数是Objects.hash(),它使用对象的各个字段进行哈希计算。如果可能,可以自定义一个哈希函数,以使键尽可能均匀地分布到内部数组中。

// 自定义哈希函数
public int customHash(String key) {
    // 自定义的哈希计算逻辑
    // ...
    return hash;
}
  1. 调整数组大小

当发现哈希冲突过多时,可以尝试调整内部数组的大小。这可以通过在创建HashMap时指定初始容量和负载因子来实现。

// 创建HashMap时指定初始容量和负载因子
HashMap<String, String> map = new HashMap<>(initialCapacity, loadFactor);
  1. 使用其他数据结构

如果发现HashMap的性能不佳,可以考虑使用其他数据结构,如TreeMapLinkedHashMap。例如,TreeMap通过红黑树数据结构处理哈希冲突,LinkedHashMap通过维护一个运行于所有条目的双向链表来处理哈希冲突。

// 使用TreeMap代替HashMap
TreeMap<String, String> treeMap = new TreeMap<>();
treeMap.put("key", "value");
String value = treeMap.get("key"); // 获取值
  1. 避免使用频繁变动的键

如果一个对象的哈希码被改变,那么该对象就不再适合作为HashMap的键。因此,如果使用可变对象作为键,需要注意在修改对象后重新计算哈希码,或者使用其他方式来避免哈希冲突。例如,可以使用不可变对象作为键。

// 使用不可变对象作为键
public class ImmutableKey {
    private final int value;
    public ImmutableKey(int value) { this.value = value; }
    public int getValue() { return value; }
    // 重写hashCode和equals方法,保证不变性
}
ImmutableKey key = new ImmutableKey(123);
HashMap<ImmutableKey, String> map = new HashMap<>();
map.put(key, "value"); // 添加键值对
String value = map.get(key); // 获取值

以上是一些使用Java代码来避免HashMap get方法的哈希冲突的方法。根据具体的使用场景和需求,可以选择合适的方法来优化HashMap的性能。


??HashMap get方法的优缺点有哪些


HashMap的get方法具有以下优点和缺点:

优点:


1. 高效性:HashMap使用哈希表数据结构,通过哈希函数将键值对映射到数组的特定位置,使得查找、插入和删除操作的时间复杂度接近O(1)。


2. 灵活性:HashMap允许使用任何对象作为键和值,并且可以根据需要自定义哈希函数和比较器。这使得HashMap在数据结构方面非常灵活,可以适应不同的应用场景。


3. 无序性:HashMap中的键值对是无序的,即它们的存储和访问顺序无关。这使得HashMap在处理大量数据时能够提供稳定的性能表现。


缺点:


1. 哈希冲突:虽然HashMap使用哈希函数将键映射到数组的特定位置,但是由于不同的键可能具有相同的哈希值,因此仍然存在哈希冲突的问题。当哈希冲突较多时,会降低HashMap的性能。


2. 空间消耗:HashMap需要额外的空间来存储键值对以及用于维护哈希表的数据结构。因此,如果数据量很大,可能会占用较多的内存空间。


3. 线程不安全:HashMap不是线程安全的,如果在多线程环境下使用HashMap,可能会导致数据不一致或其他并发问题。需要使用额外的同步机制或者使用线程安全的替代品,例如ConcurrentHashMap。


??HashMap get方法的是线程安全的吗


HashMap的get方法不是线程安全的。在多线程环境下,如果多个线程同时访问HashMap,可能会引发数据不一致或其他并发问题。


如果需要在多线程环境下使用HashMap,可以考虑使用线程安全的替代品,例如ConcurrentHashMapConcurrentHashMap是Java中的一个线程安全哈希表实现,它使用分段锁技术来保证线程安全。与HashMap相比,ConcurrentHashMap在多线程环境下具有更好的性能表现。


另外,如果只是读操作而不涉及写操作,可以考虑使用只读集合,例如Collections.unmodifiableMap()方法返回的不可修改Map,或者使用线程安全的只读替代品,例如UnmodifiableConcurrentMap。这些只读集合或只读替代品可以避免不必要的同步开销,提高性能。


总之,在多线程环境下使用HashMap时需要注意线程安全问题,并选择合适的线程安全替代品或同步机制来保证数据的一致性和正确性。


看一个Demo吧:


/**
*   HashMap的get方法在多线程环境下的不安全性
*/

import java.util.HashMap;  
  
public class HashMapExample {  
    public static void main(String[] args) {  
        // 创建一个HashMap  
        HashMap<String, String> map = new HashMap<>();  
        map.put("key1", "value1");  
        map.put("key2", "value2");  
        map.put("key3", "value3");  
  
        // 创建两个线程,同时访问HashMap的get方法  
        Thread thread1 = new Thread(() -> {  
            for (int i = 0; i < 1000; i++) {  
                String value = map.get("key1");  
                System.out.println("Thread 1: " + value);  
            }  
        });  
  
        Thread thread2 = new Thread(() -> {  
            for (int i = 0; i < 1000; i++) {  
                String value = map.get("key2");  
                System.out.println("Thread 2: " + value);  
            }  
        });  
  
        // 启动线程  
        thread1.start();  
        thread2.start();  
    }  
}

在上面的Demo中,创建了一个HashMap并向其中添加了三个键值对。然后,创建了两个线程,每个线程都使用HashMap的get方法来获取键值对。由于HashMap的get方法不是线程安全的,因此在多线程环境下,可能会出现数据不一致或其他并发问题。因此,在多线程环境下使用HashMap时,需要特别小心并考虑使用线程安全的替代品或同步机制来保证数据的一致性和正确性。


再看一个Demo吧:



/**
*   如何使用Java的并发工具类ConcurrentHashMap来替代HashMap,以确保线程安全
*/
import java.util.concurrent.ConcurrentHashMap;  
  
public class ConcurrentHashMapExample {  
    public static void main(String[] args) {  
        // 创建一个ConcurrentHashMap  
        ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();  
        concurrentMap.put("key1", "value1");  
        concurrentMap.put("key2", "value2");  
        concurrentMap.put("key3", "value3");  
  
        // 创建两个线程,同时访问ConcurrentHashMap的get方法  
        Thread thread1 = new Thread(() -> {  
            for (int i = 0; i < 1000; i++) {  
                String value = concurrentMap.get("key1");  
                System.out.println("Thread 1: " + value);  
            }  
        });  
  
        Thread thread2 = new Thread(() -> {  
            for (int i = 0; i < 1000; i++) {  
                String value = concurrentMap.get("key2");  
                System.out.println("Thread 2: " + value);  
            }  
        });  
  
        // 启动线程  
        thread1.start();  
        thread2.start();  
    }  
}

在这个Demo中,使用了ConcurrentHashMap来替代HashMap。ConcurrentHashMap是Java中的一个线程安全哈希表实现,它使用分段锁技术来保证线程安全。因此,即使在多线程环境下,ConcurrentHashMap的get方法也是安全的,不会出现数据不一致或其他并发问题。通过使用ConcurrentHashMap,我们可以避免使用额外的同步机制或线程安全的替代品,从而简化代码并提高性能。


??什么是ConcurrentHashMap


ConcurrentHashMap是Java中的一个线程安全的哈希表实现,它是HashMap的一个并发版本。在多线程环境中,ConcurrentHashMap提供高效的并发访问。

ConcurrentHashMap在实现上采用了分段锁的机制,将整个哈希表分成多个段,每个段都有自己的锁。当多个线程同时访问ConcurrentHashMap时,它们只需要竞争某个段上的锁,而不是整个哈希表的锁,从而提高了并发性能。

因此,ConcurrentHashMap在并发编程中是一种常用的数据结构,用于在多线程环境下安全地进行数据访问和修改。

??ConcurrentHashMap有哪些应用场景


ConcurrentHashMap的应用场景主要包括需要高并发访问和修改的场景,尤其是在多线程环境下。以下是一些常见的应用场景:

  1. 共享数据存储:在高并发访问情况下,多个线程同时对数据进行读写操作,需要使用ConcurrentHashMap作为共享数据存储,以保证数据的一致性和正确性。

  1. 数据缓存:ConcurrentHashMap可以作为线程安全的缓存实现,用来存储经常访问的数据。多个线程可以同时读取缓存数据,而不会相互干扰。

  1. 任务调度:在多线程任务调度系统中,可以使用ConcurrentHashMap来存储和管理任务。线程可以安全地获取、修改和删除任务,而不会出现死锁或数据不一致的问题。

  1. 分布式系统:在分布式系统中,ConcurrentHashMap可以用于实现分布式锁或者分布式数据存储。多个节点可以同时访问和修改数据,而不会出现冲突或数据不一致的问题。

  1. 数据库连接池:数据库连接池可以使用ConcurrentHashMap来管理连接。多个线程可以同时获取、释放连接,而不会相互干扰。

  1. 事件驱动系统:在事件驱动系统中,ConcurrentHashMap可以用于存储事件和监听器。多个线程可以同时发布和消费事件,而不会出现数据不一致或死锁的问题。

需要注意的是,尽管ConcurrentHashMap提供了线程安全的并发访问,但在使用时仍需注意避免死循环和其他线程相关的问题。另外,如果只需要对数据进行单线程操作,则可以选择使用HashMap或其他非线程安全的数据结构,以提高性能。


??ConcurrentHashMap的优缺点


ConcurrentHashMap是Java中的一个线程安全的哈希表实现,它提供高效的并发访问。以下是一些ConcurrentHashMap的优缺点:

优点:


  1. 线程安全:ConcurrentHashMap在多线程环境下提供安全的访问和修改,不会出现数据不一致或死锁的问题。

  1. 高并发性能:通过分段锁的机制,ConcurrentHashMap能够支持高并发的读写操作,提高了系统的吞吐量和响应速度。

  1. 动态扩容:ConcurrentHashMap能够自动进行扩容,以适应数据量的增长。

  1. 易于使用:ConcurrentHashMap提供了丰富的API,方便进行数据的添加、删除、查找等操作。

缺点:


  1. 内存消耗较大:由于ConcurrentHashMap使用了额外的锁和数据结构来保证线程安全,因此相对于HashMap,其内存消耗会更大。

  1. 写操作性能略低:由于ConcurrentHashMap在写操作时需要获取锁,因此在高并发场景下,写操作的性能可能会略低于HashMap。

  1. 不支持完全有序:ConcurrentHashMap的迭代器并不保证元素的顺序,虽然其内部元素的顺序是确定的,但外部迭代器无法保证顺序。

  1. 不保证强一致性:在某些情况下,ConcurrentHashMap可能不会立即反映出所有的并发修改。虽然这通常不会导致问题,但在某些特定场景下可能需要额外的处理。

注意:尽管ConcurrentHashMap具有上述优点和缺点,但在实际应用中,其线程安全和高并发性能的优点往往更加突出,因此被广泛使用在需要高并发访问和修改的场景中。


??源码解读环节(每一行都加了注释方便快速透彻)


public V get(Object key) {
	Node<k,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}

get 方法看起来很简单,就是通过同样的 hash 得到 key 的hash 值。重点看下 getNode方法:


final Node<k,V> getNode(int hash, Object key) {
	//当前HashMap的散列表的引用
	Node<KV>[] tab;
	//first:桶头元素
	//e: 用于存放临时元素
	Node<KV> first, e;
	//n: table 数组的长度
	int n;
	//元素中的 k
	K k;
	// 将 table 赋值为 tab,不等于null 说明有数据,(n = tab.ength) > 同理说明 table 中有数据
	//同时将 该位置的元素 赋值为 first
	if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
		//定位到了桶的到的位置的元素就是想要获取的 key 对应的,直接返回该元素
		if (first.hash == hash && ((k = first.key) == key  ||(key != null && key.equals(k)))) {
			return first;
		}
		//到这一步说明定位到的元素不是想要的,且该位置不仅仅有一个元素,需要判断是链表还是树
		if ((e = first.next) != null) {
			//是否已经树化
			if (first instanceof TreeNode) {
				return ((TreeNode<KV>) first).getTreeNode(hash, key);
			}
			//处理链表的情况
			do {
				//如果遍历到了就直接返回该元素
				if (e.hash == hash && ((k = e.key) == key  ||(key != null 88 key.equals(k)))) {
					return e;
				}
			} while ((e = e.next) != null);
		}
	}
	//遍历不到返回nu11
	return null;
}

文章来源:https://blog.csdn.net/Java_Yangxiaoyuan/article/details/135467737
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。