怎样弄免费网站,有服务器有域名怎么做网站,北京简网世纪科技有限公司,自己做的影视会员网站违法么一、核心特性
HashMap集合的key是无序不可重复的。 ①无序#xff1a;插入顺序和取出顺序不一定相同。 ②不可重复#xff1a;key具有唯一性。 向HashMap集合中put时#xff0c;key如果重复的话#xff0c;value会覆盖。
二、HashMap集合的key具有唯一性#xff0c;向ke…一、核心特性
HashMap集合的key是无序不可重复的。 ①无序插入顺序和取出顺序不一定相同。 ②不可重复key具有唯一性。 向HashMap集合中put时key如果重复的话value会覆盖。
二、HashMap集合的key具有唯一性向key部分插入自定义的类型会怎样
当向 HashMap 的 key 部分插入自定义类型时其行为取决于你是否正确重写了 hashCode() 和 equals() 方法。以下是不同场景下的表现
1. 未重写 hashCode 和 equals
默认使用 Object 类的 hashCode()基于内存地址生成哈希值和 equals()比较内存地址是否相同。 结果 即使两个对象的内容完全相同也会被 HashMap 视为不同的 key导致重复插入破坏 key 的唯一性
示例代码
User类
public class User {private String name;private int age;public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}
}
测试类
import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest1 {public static void main(String[] args) {// Map集合的key部分存储的是自定义的类型MapUser, Integer map new HashMap();// 准备User对象User user1 new User(zhangsan, 20);User user2 new User(lisi, 22);User user3 new User(wangwu, 21);User user4 new User(zhaoliu, 19);User user5 new User(zhaoliu, 19);// 向Map集合中putkeyvaluemap.put(user1, 110);map.put(user2, 111);map.put(user3, 112);map.put(user4, 113);map.put(user5, 114);// 遍历SetUser users map.keySet();for(User user : users){Integer value map.get(user);System.out.println(user value);}}
}
运行结果 2. 仅重写 equals未重写 hashCode
若两个对象 equals() 返回 true但 hashCode() 不同HashMap 会将它们分配到不同的哈希桶中。 结果 HashMap 无法正确识别它们是“相同”的 key仍会重复插入。
User类
public class User {private String name;private int age;public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object obj) {//如果name一样age也一样就表示同一个用户if(objnull)return false;if(objthis)return true;if(obj instanceof User){User user(User) obj;return user.getName().equals(this.getName())user.getAge()this.getAge();}return false;}}
测试类
import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest1 {public static void main(String[] args) {// Map集合的key部分存储的是自定义的类型MapUser, Integer map new HashMap();// 准备User对象User user1 new User(zhangsan, 20);User user2 new User(lisi, 22);User user3 new User(wangwu, 21);User user4 new User(zhaoliu, 19);User user5 new User(zhaoliu, 19);// 向Map集合中putkeyvaluemap.put(user1, 110);map.put(user2, 111);map.put(user3, 112);map.put(user4, 113);map.put(user5, 114);// 遍历SetUser users map.keySet();for(User user : users){Integer value map.get(user);System.out.println(user value);}}
}
运行结果 3. 正确重写 hashCode 和 equals
如果equals方法返回的结果是true。
那么hashCode()方法返回的结果就必须相同。这样才能保证key是不重复的。
存放在HashMap集合key部分的元素以及存储在HashSet集合中的元素都需要同时重写hashCodeequals
HashMap 通过以下步骤保证 key 的唯一性 计算哈希值用 hashCode() 确定 key 所属的哈希桶。 冲突处理在同一个哈希桶内用 equals() 检查是否存在内容相同的 key。
结果 内容相同的 key 会被视为同一个 key后插入的 value 会覆盖之前的 value。
User类重写了equals方法和hashcode方法
import java.util.Objects;public class User {private String name;private int age;public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;User user (User) o;return age user.age Objects.equals(name, user.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}
}
测试类
import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest1 {public static void main(String[] args) {// Map集合的key部分存储的是自定义的类型MapUser, Integer map new HashMap();// 准备User对象User user1 new User(zhangsan, 20);User user2 new User(lisi, 22);User user3 new User(wangwu, 21);User user4 new User(zhaoliu, 19);User user5 new User(zhaoliu, 19);// 向Map集合中putkeyvaluemap.put(user1, 110);map.put(user2, 111);map.put(user3, 112);map.put(user4, 113);map.put(user5, 114);// 遍历SetUser users map.keySet();for(User user : users){Integer value map.get(user);System.out.println(user value);}}
}
运行结果 三、HashMap 底层数据结构详解 HashMap 的底层实现是一个高效的哈希表结构结合了 数组、链表和红黑树 的优势具体设计如下 1. 核心结构数组 链表 红黑树
数组哈希桶 数组是哈希表的主干每个数组元素称为一个 桶Bucket。通过哈希函数将键Key映射到数组的特定索引位置实现 O(1) 时间复杂度的快速定位。 NodeK,V[] table; // 数组结构每个元素是一个链表的头节点或红黑树的根节点
链表 当不同的键映射到同一个桶时哈希冲突这些键值对会以 链表 形式存储。链表解决冲突但查询效率为 O(n)。 static class NodeK,V { // 链表节点结构final int hash;final K key;V value;NodeK,V next;
}
红黑树 Java 8 优化当链表长度 ≥8 且数组长度 ≥64 时链表转换为 红黑树查询效率提升至 O(logn)当节点数 ≤6 时红黑树退化为链表。
static final class TreeNodeK,V extends LinkedHashMap.EntryK,V { // 红黑树节点TreeNodeK,V parent;TreeNodeK,V left;TreeNodeK,V right;TreeNodeK,V prev;boolean red;
} 2.哈希表存储原理
(1) 哈希表Hash Table 本质一种结合 数组快速定位 和 链表/红黑树动态扩展 的数据结构。 核心组成 数组用于直接定位元素时间复杂度 O(1)。 链表/红黑树解决哈希冲突平衡查询与插入效率。 (2) 哈希函数Hash Function 作用将任意对象映射为一个整数哈希值。 Java 实现hashCode() 方法返回初始哈希值但 HashMap 会进一步处理 // HashMap 内部对哈希值的优化处理扰动函数
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 要求好的哈希函数应让不同对象尽量映射到不同的哈希值减少碰撞。
(3) 哈希碰撞Hash Collision 定义不同对象计算出的 数组索引相同即 (hash (n-1)) 结果相同。 解决方式 链表法同一索引位置的元素形成链表Java 8 前。 红黑树优化链表长度 ≥8 且数组长度 ≥64 时转为红黑树Java 8。 3.重写规范 规则 1若 equals() 返回 true则 hashCode() 必须相同。 规则 2hashCode() 相同的对象equals() 不一定返回 true允许哈希碰撞。 正确示例
class Student {String id;Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return Objects.equals(id, student.id);}Overridepublic int hashCode() {return Objects.hash(id); // 基于 id 生成哈希值}
}
4. 哈希碰撞的底层处理流程
(1) 插入键值对 (key, value) 计算哈希值hash hash(key.hashCode())。 定位桶索引index (n - 1) hash等价于 hash % n。 处理冲突 情况 1桶为空 → 直接插入新节点。 情况 2桶为链表 → 遍历链表若找到相同 key 则覆盖 value否则添加到链表尾部。 情况 3桶为红黑树 → 调用红黑树的插入方法。 (2) 链表转红黑树的阈值
条件动作链表长度 ≥8 且 数组长度 ≥64链表 → 红黑树红黑树节点数 ≤6红黑树 → 链表
5.HashMap集合的key可以是null吗 可以key是null但肯定是只能有一个。
规则如果key是null直接存到下标为0的数组里
public class oop3 {public static void main(String[] args) {MapString, String map new HashMap();map.put(null, zhangsan);map.put(null, lisi);map.put(null, wangwu);map.put(null, zhaoliu);System.out.println(map.size());SetMap.EntryString, String entries map.entrySet();for(Map.EntryString, String entry : entries){System.out.println(entry.getKey() entry.getValue());}}
}
运行结果; 四、手写HashMap
MyHashMap类
/*** 手写HashMap集合的put方法和get方法。*/
public class MyHashMapK,V {/*** 哈希表*/private NodeK,V[] table;/*** 键值对的个数*/private int size;SuppressWarnings(unchecked)public MyHashMap() {// 注意new数组的时候不能使用泛型。这样写是错误的new NodeK,V[16];this.table new Node[16];}static class NodeK,V{/*** key的hashCode()方法的返回值。* 哈希值,哈希码*/int hash;/*** key*/K key;/*** value*/V value;/*** 下一个结点的内存地址*/NodeK,V next;/*** 构造一个结点对象* param hash 哈希值* param key 键* param value 值* param next 下一个结点地址*/public Node(int hash, K key, V value, NodeK, V next) {this.hash hash;this.key key;this.value value;this.next next;}Overridepublic String toString(){return [key, value];}}/*** 获取集合中的键值对的个数* return 个数*/public int size(){return size;}/*** 向MyHashMap集合中添加一个键值对。* param key 键* param value 值* return value如果key重复则返回oldValue如果key不重复则返回newValue*/public V put(K key, V value){/*【第一步】处理key为null的情况如果添加键值对的key就是null则将该键值对存储到table数组索引为0的位置。【第二步】获得key对象的哈希值如果添加键值对的key不是null则就调用key的hashcode()方法获得key的哈希值。【第三步】获得键值对的存储位置因为获得的哈希值在数组合法索引范围之外因此我们就需要将获得的哈希值转化为[0数组长度-1]范围的整数那么可以通过取模法来实现也就是通过“哈希值 % 数组长度”来获得索引位置i。【第四步】将键值对添加到table数组中当table[i]返回结果为null时则键键值对封装为Node对象并存入到table[i]的位置。当table[i]返回结果不为null时则意味着table[i]存储的是单链表。我们首先遍历单链表如果遍历出来节点的key和添加键值对的key相同那么就执行覆盖操作如果遍历出来节点的key和添加键值对的key都不同则就将键键值对封装为Node对象并插入到单链表末尾。*/if(key null){return putForNullKey(value);}// 程序执行到此处说明key不是null// 获取哈希值int hash key.hashCode();// 将哈希值转换成数组的下标int index Math.abs(hash % table.length);// 取出下标index位置的NodeNodeK,V node table[index];if(null node){table[index] new Node(hash, key, value, null);size;return value;}// 有单向链表遍历单向链表尾插法NodeK,V prev null;while(null ! node){if(node.key.equals(key)){V oldValue node.value;node.value value;return oldValue;}prev node;node node.next;}prev.next new Node(hash, key, value, null);size;return value;}private V putForNullKey(V value) {NodeK,V node table[0];if(node null){table[0] new Node(0, null,value,null);size;return value;}// 程序可以执行到此处说明下标为0的位置上有单向链表NodeK, V prev null;while(node ! null){if(node.key null){V oldValue node.value;node.value value;return oldValue;}prev node;node node.next;}prev.next new Node(0, null,value,null);size;return value;}/*** 通过key获取value* param key 键* return 值*/public V get(K key){/*【第一步】处理key为null的情况如果查询的key就是null则就在table数组索引为0的位置去查询。【第二步】获得key对象的哈希值如果查询的key不是null则就调用key的hashcode()方法获得key的哈希值。【第三步】获得键值对的存储位置因为获得的哈希值在数组合法索引范围之外因此我们就需要将获得的哈希值转化为[0数组长度-1]范围的整数那么可以通过取模法来实现也就是通过“哈希值 % 数组长度”来获得索引位置i。【第四步】遍历单链表根据key获得value值如果table[i]返回的结果为null则证明单链表不存在那么返回null即可如果table[i]返回的结果不为null时则证明单链表存在那么就遍历整个单链表。如果遍历出来节点的key和查询的key相同那么就返回遍历出来节点的value值如果整个单链表遍历完毕则遍历出来节点的key和查询的key都不相等那么就证明查询key在链表中不存在则直接返回null即可。*/if(null key){NodeK,V node table[0];if(null node){return null;}// 程序执行到这里数组下标为0的位置不是null。就是有单向链表。while(node ! null){if(null node.key){return node.value;}node node.next;}}// key不是nullint hash key.hashCode();int index Math.abs(hash % table.length);NodeK,V node table[index];if(null node){return null;}while(null ! node){if(node.key.equals(key)){return node.value;}node node.next;}return null;}/*** 重写toString方法直接输出Map集合是会调用。* return */Overridepublic String toString(){StringBuilder sb new StringBuilder();for (int i 0; i table.length; i) {NodeK,V node table[i];// 如果node不是空就遍历整个单向链表while(node ! null){sb.append(node);node node.next;}}return sb.toString();}
}
MyHashMapTest类
/*** 测试自己编写的HashMap集合的方法。*/
public class MyHashMapTest {public static void main(String[] args) {MyHashMapString,String map new MyHashMap();map.put(110, 张三);map.put(120, 李四);map.put(130, 王五);map.put(140, 赵六);map.put(110, 张三2);map.put(null, 钱七1);map.put(null, 钱七2);map.put(null, 钱七3);map.put(null, 钱七4);System.out.println(map);System.out.println(map.get(null));System.out.println(map.get(110));System.out.println(map.get(120));MyHashMapUser, String userMap new MyHashMap();User user1 new User(张三, 20);User user2 new User(李四, 22);User user3 new User(王五, 23);User user4 new User(王五, 23);userMap.put(user1, 110);userMap.put(user2, 120);userMap.put(user3, 130);userMap.put(user4, abc);System.out.println(userMap);}
}
五、HashMap在Java8后的改进包含Java8
1.初始化时机
Java8之前构造方法执行时初始化table数组。
Java8之后第一次调用put方法时初始化table数组。
2.插入法 Java8之前头插法 Java8之后尾插法 3.数据结构 Java8之前数组 单向链表 Java8之后数组 单向链表 红黑树。 最开始使用单向链表解决哈希冲突。如果结点数量 8并且table的长度 64。单向链表转换为红黑树。 当删除红黑树上的结点时结点数量 6 时。红黑树转换为单向链表。 六、HashMap初始化容量永远都是2的次幂
HashMap集合初始化容量16第一次调用put方法时初始化
HashMap集合的容量永远都是2的次幂假如给定初始化容量为31它底层也会变成32的容量。
将容量设置为2的次幂作用是加快哈希计算减少哈希冲突。
为什么会加快哈希计算
首先你要知道使用二进制运算是最快的。
当一个数字是2的次幂时例如数组的长度是2的次幂
hash (length-1) 的结果和 hash % length的结果相同。
注意只有是2的次幂时以上等式才会成立。因为了使用 运算符让效率提升因此建议容量一直是2的次幂。
为什么会减少哈希冲突
底层运算是hash length - 1
如果length是偶数length-1后一定是奇数奇数二进制位最后一位一定是1,1和其他二进制位进行与运算结果可能是1也可能是0这样可以减少哈希冲突让散列分布更加均匀。
如果length是奇数length-1后一定是偶数偶数二进制位最后一位一定是0,0和任何数进行与运算结果一定是0这样就会导致发生大量的哈希冲突白白浪费了一半的空间。
/*** 测试HashMap集合的容量是否一直都是2的次幂。* 为什么原因有二* 第一提高哈希计算的效率。位运算肯定比%取模操作速度快。* 第二减少哈希冲突。让散列分布更加均匀。*/
public class oop3 {public static void main(String[] args) {MapString, String map new HashMap(50);int length (int)Math.pow(2, 6);System.out.println(length); // 2048// 使用取模 % 进行哈希计算int hash 张三.hashCode();int index hash % length;System.out.println(index); // 745// 使用 进行哈希计算/*假设length是偶数length - 1结果一定是奇数。hash length - 1;这个式子中 length - 1 是奇数。奇数的二进制位的最后一位一定是1.length - 1计算之后的结果对应的二进制位最低位一定是1.也就是xxxxxxxxxxxxxxxxxxxx1然后拿着这个二进制位和hash进行与操作hash可能得二进制位是yyyyyyyyyyyyyyyyyyyy0也可能是yyyyyyyyyyyyyyyyyyyy1xxxxxxxxxxxxxxxxxxxx1 (length - 1) yyyyyyyyyyyyyyyyyyyy0 hash----------------------------zzzzzzzzzzzzzzzzzzzz0 (index) 是偶数xxxxxxxxxxxxxxxxxxxx1 (length - 1) yyyyyyyyyyyyyyyyyyyy1 hash-----------------------------zzzzzzzzzzzzzzzzzzzz1index是奇数假设length是奇数那么lenght - 1一定是偶数。它一定是xxxxxxxxxxxxxxxxxxxxx0hash值可能是yyyyyyyyyyyyyyyyyyyyy1也可能是yyyyyyyyyyyyyyyyyyyyy0xxxxxxxxxxxxxxxxxxxxx0 length-1yyyyyyyyyyyyyyyyyyyyy1 hash-------------------------------zzzzzzzzzzzzzzzzzzzzz0 一定是偶数xxxxxxxxxxxxxxxxxxxxx0 length-1yyyyyyyyyyyyyyyyyyyyy0 hash-------------------------------zzzzzzzzzzzzzzzzzzzzz0 一定是偶数*/int index2 hash length - 1;System.out.println(index2); // 745}
}运行结果; 七、关于 HashMap 初始化容量
当创建一个 HashMap 对象并设置初始容量为 15 时哈希表的实际容量会被自动调整为 16。
原因解析
HashMap 的容量即底层数组的长度必须为 2 的幂次方如 16、32、64 等。这一设计的核心目的是优化哈希计算和元素分布 哈希计算优化通过位运算 (n - 1) hash 替代取模运算 hash % n效率更高。 均匀分布元素当 n 是 2 的幂次方时n - 1 的二进制形式为全 1例如 16-115 → 1111与哈希值的与运算能更均匀地分散元素到不同桶中。 若用户指定的初始容量不是 2 的幂次方HashMap 会通过 tableSizeFor() 方法自动调整为 大于等于该值的最小 2 的幂次方。例如 指定容量为 15 → 实际容量为 16。 指定容量为 17 → 实际容量为 32。 底层源码验证
HashMap 的 tableSizeFor() 方法负责调整容量
static final int tableSizeFor(int cap) {int n cap - 1; // 防止 cap 本身是 2 的幂次方时重复扩容n | n 1; // 通过位运算将最高位后的所有位变为 1n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}
示例计算cap 15 n 15 - 1 14二进制 1110。 依次右移并执行按位或操作 n | n 1 → 1110 | 0111 1111
n | n 2 → 1111 | 0011 1111
...后续操作不再改变结果 最终 n 1 15 1 16。 性能优化建议 避免频繁扩容 若预计存储 N 个元素建议设置初始容量为 N / loadFactor 1向上取整到最近的 2 的幂次方。 示例 预计存储 1000 个元素负载因子默认 0.75 初始容量 1000 / 0.75 1 ≈ 1334 → 调整为 2048最近的 2 的幂次方。 权衡空间与时间 过大的初始容量会浪费内存需根据实际场景平衡。 总结
用户指定容量HashMap 实际容量调整规则1516大于等于 15 的最小 2 的幂1732大于等于 17 的最小 2 的幂10241024本身已是 2 的幂
理解这一机制可以更精准地设置初始容量避免扩容带来的性能损耗。
