hashmap 在 put 时,新链表节点是放在头部还是尾部

HashMap的实现是基于哈希表（Hash Table）的数据结构。在使用HashMap的put方法插入新节点时，新节点的插入位置是在链表的头部。

当我们向HashMap中插入新的键值对时，首先会根据键的哈希值计算出数组的索引位置。如果该索引位置已经存在链表节点，则需要进行链表的遍历，直到找到链表的尾部节点。然后在链表的尾部插入新的节点，将插入的节点设置为链表的尾部。

但是，如果链表是空的，也就是该索引位置没有任何元素和节点。那么新节点将会被直接插入到链表的头部，成为新的头节点。其原因是，当链表为空时，无需遍历链表，直接将新节点插入到头部，省去了多余的操作。

采用将新节点插入到链表的头部的方式，是因为在哈希表中，链表的顺序并不重要。HashMap的put操作主要考虑的是时间复杂度的最优化，因此选择了在链表的头部进行插入，这样可以保证对于任何输入，都能够在较短的时间内找到并插入到正确的位置。

总的来说，HashMap在put操作时，新链表节点会被放在链表头部。这样操作的好处是，无论链表是否为空，都可以在常数时间内完成插入操作，提高了插入的效率。

相关问题

HashMap 底层实现原理是什么？JDK8 做了哪些优化？

### 回答1：
HashMap 是一种哈希表实现的映射。它存储键值对，允许用户快速查找特定键对应的值。

HashMap 底层是通过数组和链表实现的。它将键哈希成一个整数，然后将键值对存储在数组中的对应位置。如果多个键值对映射到了同一个数组位置，它们就会按照链表的形式连接起来。

在 JDK8 中，HashMap 做了以下优化：

1. 当链表长度大于某个阈值（默认为 8）时，会自动转换为红黑树。这样可以使查询的时间复杂度从 O(n) 降低到 O(log n)。

2. 当哈希表中的实际大小（键值对数量）超过哈希表数组的大小时，会自动将哈希表数组的大小增加一倍。这样可以减少碰撞的次数，提高查询效率。

3. 引入了“红色哈希码”（fusing hash code）技术，可以通过一个状态位来标识一个节点是否被搬迁过。这样可以在查询时避免对节点的额外访问，提高查询效率。

### 回答2：
HashMap 底层实现原理是基于数组和链表 （JDK1.7及之前版本）或者数组和红黑树（JDK1.8及之后版本）的组合实现。

在JDK1.7及之前版本中，HashMap采用数组和链表的组合实现。当往HashMap中添加一个键值对时，首先根据键的hashCode值确定它在数组中的位置（下标），如果该位置没有元素，就直接将该键值对插入该位置；如果该位置已经有元素（即有冲突发生），则通过比较键的hashCode值以及equals方法来判断是否是相同的键，如果是相同的键，则覆盖该键的值；如果不是相同的键，则将新的键值对插入到链表的下一个位置。

在JDK1.8及之后版本中，当链表中的元素超过一定的阈值（默认为8），链表会转变为红黑树，通过红黑树的平均查询时间复杂度为O(logn)来提升查询性能。这是因为在链表中，查询效率随着链表长度的增加而线性增加，而红黑树的查询效率近似于O(logn)。

JDK8还做了以下优化：
1. 使用红黑树替代链表：当链表长度超过阈值时，将链表转为红黑树，提高查询效率。
2. 引入红黑树的目的是为了解决JDK1.7及之前版本中链表过长导致的查询性能退化问题。
3. 优化了扩容机制：在JDK1.7中，扩容时需要重新计算所有元素的位置，而在JDK1.8中，只需要重新计算新增元素的位置，减少了时间复杂度。
4. 使用了TreeBin类：作为红黑树的实现，继承自Node类，并实现了Map.Entry接口。
5. 添加了红黑树的插入和删除操作：用于维护红黑树的平衡性。
总而言之，JDK8对HashMap做了优化，使用红黑树替代链表以提高查询性能，并优化了扩容机制，使得HashMap在处理大量数据时能够更有效地进行操作。

### 回答3：
HashMap底层实现原理是基于哈希表（Hash Table）的数据结构。HashMap通过将键对象进行哈希运算，得到对应的哈希值，并将该键值对存储在哈希值对应的桶（Bucket）中。在JDK8中，HashMap的底层实现由数组和链表结合而成的链表散列结构。

具体来说，HashMap底层实现原理有以下几个要点：
1. 初始时会创建一个长度为16的数组，数组的每个元素是一个链表的头节点。
2. 当往HashMap中put新的键值对时，首先会计算键的哈希值。
3. 根据哈希值得到对应的数组索引，如果该索引位置为空，则直接将键值对插入到该位置。
4. 如果该索引位置已经存在链表，会遍历链表，查找是否已经存在相同的键，如果存在，则更新对应的值；如果不存在，则将该键值对插入到链表的尾部。
5. 当链表长度达到一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。
6. 当数组的使用率超过加载因子（默认为0.75）时，将触发数组扩容操作，将数组长度扩大一倍，并重新计算每个键值对在数组中的位置。

在JDK8中，HashMap进行了以下优化：
1. 引入了红黑树，使得在链表长度较长时，查找效率更高。
2. 在哈希碰撞（Hash Collision）较多时，链表转化为红黑树的阈值由原来的8改为了原来的6，减少了时间和空间的消耗。
3. 在插入新元素时，如果发生了哈希碰撞，在链表长度小于8时，新的节点会插入到链表的头部，而不是尾部，以提升查询性能。
4. 数组扩容时，采用了批量迁移的方式，减少了rehash的次数，提升了性能。
5. 在并发环境下，通过引入并发控制手段，提高了HashMap的并发性能。例如，使用了synchronized关键字和CAS操作。

总的来说，JDK8对HashMap底层实现进行了较多的优化，提高了性能和并发性能。

请用java链表来实现LRU缓存淘汰策略呢

### 回答1：

可以使用java中的LinkedHashMap类来实现LRU缓存淘汰策略。LinkedHashMap是一种特殊的HashMap，它不仅保存了键值对，还维护了一个双向链表来记录插入顺序，当缓存满后，它会将最先插入的元素淘汰掉。

### 回答2：
LRU（最近最少使用）缓存淘汰策略是指在缓存满时，优先淘汰最近最少使用的数据。实现LRU缓存淘汰策略可以使用链表和哈希表的组合。

首先，我们可以创建一个双向链表的节点类，包含键值对的信息，以及前后指针。链表的头部表示最近访问的节点，尾部表示最久未使用的节点。

我们还需要一个哈希表，用于快速查找节点。哈希表的键是缓存的键，值是对应的节点。

接下来，我们需要实现缓存淘汰策略的几个操作：

1. 获取操作：当尝试获取缓存中的键值对时，如果哈希表中存在该键，则将对应的节点移动到链表头部，并返回该值。如果哈希表中不存在该键，则返回空。

2. 添加操作：当添加新的键值对时，如果该键已存在于缓存中，则将该节点移到链表头部，更新值。否则，创建新节点，并将其插入到链表头部和哈希表中。如果缓存已满，删除链表尾部的节点，并在哈希表中删除对应的键。

3. 删除操作：当从缓存中删除某个键值对时，找到对应的节点，从链表中删除该节点，并在哈希表中删除该键。

以上就是使用Java链表实现LRU缓存淘汰策略的基本思路。通过使用双向链表和哈希表的组合，能够快速实现缓存的增删改查操作，并保持对节点访问的顺序，以便实现LRU策略。

### 回答3：
LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰策略，当缓存满时，会将最长时间未被使用的数据从缓存中淘汰。实现LRU缓存淘汰策略可以使用Java中的链表来实现。

Java中已经提供了LinkedList类，可以直接用于实现链表数据结构。接下来是一个简单的实现LRU缓存的示例代码：

import java.util.LinkedList;

public class LRUCache<K, V> {
    private int capacity;
    private LinkedList<Entry<K, V>> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedList<>();
    }

    public V get(K key) {
        Entry<K, V> entry = findEntryByKey(key);
        if (entry != null) {
            // 将使用的数据移动到链表头部
            cache.remove(entry);
            cache.addFirst(entry);
            return entry.value;
        }
        return null;
    }

    public void put(K key, V value) {
        Entry<K, V> entry = findEntryByKey(key);
        if (entry != null) {
            // 如果key已存在，更新其value，并将数据移动到链表头部
            entry.value = value;
            cache.remove(entry);
            cache.addFirst(entry);
        } else {
            // 如果key不存在，先判断容量是否已满，如果已满则移除最久未使用的数据
            if (cache.size() >= capacity) {
                cache.removeLast();
            }
            // 将新数据插入到链表头部
            Entry<K, V> newEntry = new Entry<>(key, value);
            cache.addFirst(newEntry);
        }
    }

    private Entry<K, V> findEntryByKey(K key) {
        for (Entry<K, V> entry : cache) {
            if (entry.key.equals(key)) {
                return entry;
            }
        }
        return null;
    }

    private static class Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

使用示例：

LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
System.out.println(cache.get("a")); // 输出1
cache.put("d", 4);
System.out.println(cache.get("b")); // 输出null，因为b是最久未使用的数据，已被淘汰

在LRUCache类中，使用LinkedList作为缓存的数据存储结构。缓存的最近使用的数据总是位于链表的头部，当需要访问或更新数据时，将其移动到链表头部。当缓存已满时，移除链表尾部的最久未使用的数据。

这种实现方式可以在O(1)的时间复杂度内实现get和put操作，符合LRU缓存淘汰策略的特性。