怎样进行网站推广,怎么做各大视频网站的会员代理,汽车网站营销,服务app开发的公司HashMap的数据结构是怎样的? ✔️HashMap的数据结构✔️ 数组✔️ 链表 ✔️HashMap的数据结构 在Java中#xff0c;保存数据有两种比较简单的数据结构: 数组和链表#xff08;或红黑树#xff09;。 HashMap是 Java 中常用的数据结构#xff0c;它实现了 Map 接口。Has… HashMap的数据结构是怎样的? ✔️HashMap的数据结构✔️ 数组✔️ 链表 ✔️HashMap的数据结构 在Java中保存数据有两种比较简单的数据结构: 数组和链表或红黑树。 HashMap是 Java 中常用的数据结构它实现了 Map 接口。HashMap通过键值对的形式存储数据其中键是唯一的而值可以是任何对象。HashMap底层使用数组和链表或红黑树来实现。 常用的哈希函数的冲突解决办法中有一种方法叫做链地址法其实就是将数组和链表组合在一起发挥了两者的优势我们可以将其理解为链表的数组。在JDK 1.8之前HashMap就是通过这种结构来存储数据的。 我们可以从上图看到左边很明显是个数组数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去反过来我们也正是通过这些特征找到正确的链表再从链表中找出正确的元素。其中根据元素特征计算元素数组下标的方法就是哈希算法即本文的主角 hash() 函数 (当然还包括indexOf()函数)。 ✔️ 数组 数组HashMap使用一个数组来存储键值对。数组的每个元素都是一个桶bucket桶中存储着一个链表LinkedList或红黑树TreeMap。桶的数量可以根据需要动态调整。数组的索引方式采用哈希算法通过将键的哈希值对数组长度取模来得到对应的桶。 数组的特点是:寻址容易插入和删除困难。 看一个如何使用数组实现HashMap的代码片段 public class MyHashMapK, V { // 默认初始容量 private static final int DEFAULT_INITIAL_CAPACITY 16; // 默认加载因子 private static final float DEFAULT_LOAD_FACTOR 0.75f; // 存储键值对的数组 private EntryK, V[] table; // 当前容量 private int capacity; // 实际存储的键值对数量 private int size; public MyHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public MyHashMap(int capacity) { this(capacity, DEFAULT_LOAD_FACTOR); } public MyHashMap(int capacity, float loadFactor) { this.capacity capacity; table new Entry[capacity]; size 0; } public V put(K key, V value) { int hash hash(key); int index indexFor(hash, table.length); EntryK, V oldValue table[index]; if (oldValue null) { table[index] new Entry(key, value, null); size; if (size capacity * loadFactor) { rehash(); } } else { EntryK, V newEntry new Entry(key, value, oldValue); table[index] newEntry; } return oldValue null ? null : oldValue.value; } public V get(K key) { int hash hash(key); int index indexFor(hash, table.length); EntryK, V entry table[index]; if (entry ! null Objects.equals(entry.key, key)) { return entry.value; } else { return null; } } public int size() { return size; } private int hash(Object key) { return Objects.hashCode(key); } private int indexFor(int hash, int length) { return hash % length; } private void rehash() { EntryK, V[] oldTable table; int oldCapacity oldTable.length; int newCapacity oldCapacity * 2; EntryK, V[] newTable new Entry[newCapacity]; for (EntryK, V oldEntry : oldTable) { while (oldEntry ! null) { EntryK, V next oldEntry.next; int hash hash(oldEntry.key); int index indexFor(hash, newCapacity); oldEntry.next newTable[index]; newTable[index] oldEntry; oldEntry next; } } table newTable; capacity newCapacity; }
}✔️ 链表 链表当多个键的哈希值映射到同一个桶时它们会形成一个链表。链表中的每个节点包含一个键值对和指向下一个节点的指针。链表的作用是在插入、删除和查找操作时解决哈希冲突。 链表的特点是: 寻址困难插入和删除容易 看一个如何使用链表实现HashMap的代码片段是一个简单的HashMap实现使用链表来处理哈希冲突 public class MyHashMapK, V { private static class EntryK, V { K key; V value; EntryK, V next; Entry(K key, V value, EntryK, V next) { this.key key; this.value value; this.next next; } } private EntryK, V[] table; private int capacity; private int size; private float loadFactor; public MyHashMap(int capacity, float loadFactor) { if (capacity 0) throw new IllegalArgumentException(Capacity must be non-negative); if (loadFactor 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Load factor must be positive); this.capacity capacity; this.loadFactor loadFactor; table new Entry[capacity]; size 0; } public V put(K key, V value) { if (key null) return null; // HashMaps dont allow null keys // If size exceeds load factor * capacity, rehash if (size capacity * loadFactor) { rehash(); } int hash hash(key); int index indexFor(hash, capacity); EntryK, V entry table[index]; if (entry null) { // No collision, create new entry table[index] new Entry(key, value, null); size; } else { // Collision occurred, handle it using chaining while (entry ! null !entry.key.equals(key)) { if (entry.next null) { // End of chain, insert new entry entry.next new Entry(key, value, null); size; break; } entry entry.next; } // If key already exists, update value if (entry ! null entry.key.equals(key)) { V oldValue entry.value; entry.value value; return oldValue; } } return null; // If key was new or not found } public V get(K key) { if (key null) return null; // HashMaps dont allow null keys int hash hash(key); int index indexFor(hash, capacity); EntryK, V entry table[index]; while (entry ! null !entry.key.equals(key)) { entry entry.next; } return entry null ? null : entry.value; } private void rehash() { capacity * 2; EntryK, V[] oldTable table; table new Entry[capacity]; size 0; for (EntryK, V entry : oldTable) { while (entry ! null) { EntryK, V next entry.next; int hash hash(entry.key); int index indexFor(hash, capacity); entry.next table[index]; table[index] entry; size; entry next; } } } private int hash(K key) { return Math.abs(key.hashCode()) % capacity; } private int indexFor(int hash, int length) { return hash % length; } public static void main(String[] args) { MyHashMapString, Integer map new MyHashMap(16, 0.75f); map.put(one, 1); map.put(two, 2); map.put(three, 3); System.out.println(map.get(one)); // Should print 1 System.out.println(map.get(two)); // Should print 2 System.out.println(map.get(three)); //Should print 3在JDK 1.8中为了解决因hash冲突导致某个链表长度过长影响 put 和 get 的效率引入了红黑树。 关于红黑树下一篇会作为单独的博文进行更新。
