1. 首页
  2. Java基础

055-五十五、Java之手写HashMap(下)

entrySet()

返回此映射所包含的映射关系的 Set 视图。

该方法实现起来还是比较麻烦的。
1.由于本方法需要返回一个Set<Map.Entry<K,V>>类型,所以需要借用一下jdk中的TreeSet集合。


/** * 仿造entrySet方法需要定义一个set集合 */ private Set<Map.Entry<K,V>> entrySet;

2.在外部类的构造方法中实例化一个TreeHast集合,现在改造外部类的有参构造方法。


/** * 有参构造 * @param defaultLength */ public MyHashMap(int defaultLength) { this.entries = new Entry[defaultLength]; //这里需要先实例化一个hashset集合 this.entrySet = new TreeSet<>(); }

3.定一个public Set&lt;Map.Entry&lt;K,V>>`` entrySet()方法


/** * 返回此映射所包含的映射关系的 Set 视图。 * @return */ public Set<Map.Entry<K,V>> entrySet() { return this.entrySet; }

4.那么上面只是定义和返回了set集合,现在该怎么将数据添加到set中呢,现在使用一个偷懒的办法。纯属自己的想法。

就是每次put的时候,顺便将元素添加到set集合中就可以了。那么现在需要改造的地方太多了,首先改造外部类的put方法。
在普通添加的时候加上这句代码 entrySet.add(entry);//在put的时候顺带将entry添加到set中


/** * 新增 * @param entry */ private void put(Entry<P,Q> entry) { /** * 表示已经有了那么需要判断key是否一致 */ if (Objects.equals(this.key, entry.key) && this.hash == entry.hash) { //表示一致直接替换value值即可 this.value = entry.value; } else {//表示可以新增了 /** * 如果next中没有元素直接赋值了 */ if (Objects.isNull(this.next)) { this.next = entry; //在put的时候顺带将entry添加到set中 entrySet.add(entry); size++;//这里也表示为新增一个元素 } else {//递归 this.next.put(entry); } } }

5.改造内部类的类型。
a.需要将内部类的泛型类型继承外部类的泛型类型


private final class Entry<P extends K,Q extends V>

不继承的话,内部类的K,V类型会和外部类的K,V重叠,因为作用域的关系会自动覆盖外部类的K,V。

b. 需要实现Comparable接口的public int compareTo(Object o)方法,因为使用TreeSet的排序的时候用到。


/** * 因为使用的TreeSet集合所以需要实现Comparable的compareTo方法 * @param o * @return */ @Override public int compareTo(Entry<P, Q> o) { return (Objects.equals(this.key, o.key) && this.hash == o.hash) ? 0 : 1; }

c.需要实现Map.Entry<K,V>接口的
public P getKey()
public Q getValue()
public Q setValue(V value)
这3个方法必须实现。因为迭代的时候需要使用到。


/** * 必须实现Map.Entry<K,V>的方法 * 使用迭代器时会使用到 * @return */ @Override public P getKey() { return this.key; } @Override public Q getValue() { return this.value; } @Override public Q setValue(V value) { return (this.value = (Q) value); }

d.需要改造内部类的所有方法的泛型类型,以及在put方法中添加元素到set集合中。添加这句代码 entrySet.add(entry);,并且需要把参数的泛型类型修改为内部类的泛型类型P,Q。


/** * 新增 * @param entry */ private void put(Entry<P,Q> entry) { /** * 表示已经有了那么需要判断key是否一致 */ if (Objects.equals(this.key, entry.key) && this.hash == entry.hash) { //表示一致直接替换value值即可 this.value = entry.value; } else {//表示可以新增了 /** * 如果next中没有元素直接赋值了 */ if (Objects.isNull(this.next)) { this.next = entry; //在put的时候顺带将entry添加到set中 entrySet.add(entry); size++;//这里也表示为新增一个元素 } else {//递归 this.next.put(entry); } } }

这里基本上重点要改造的方法就改造完了,还有其它的地方改造就是内部类的类型了,这里就直接看源码吧!!!


** * 这是一个成员内部类 * 储存hashmap元素的key和value * 要仿造entrySet方法需要实现 Comparable, Map.Entry<K,V> */ private final class Entry<P extends K,Q extends V> implements Comparable<Entry<P,Q>>, Map.Entry<K,V> { /** * key 键 */ private P key; /** * value 值 */ private Q value; /** * hash码,比较key是否重复使用 */ private long hash; /** * 数组+链表,所以就需要提供下个节点 */ private Entry<P,Q> next; /** * 构造器 * @param key * @param value */ private Entry(P key, Q value) { this.key = key; this.value = value; this.hash = this.key.hashCode(); } /** * 新增 * @param entry */ private void put(Entry<P,Q> entry) { /** * 表示已经有了那么需要判断key是否一致 */ if (Objects.equals(this.key, entry.key) && this.hash == entry.hash) { //表示一致直接替换value值即可 this.value = entry.value; } else {//表示可以新增了 /** * 如果next中没有元素直接赋值了 */ if (Objects.isNull(this.next)) { this.next = entry; //在put的时候顺带将entry添加到set中 entrySet.add(entry); size++;//这里也表示为新增一个元素 } else {//递归 this.next.put(entry); } } } /** * 获取数据 * @param key * @return */ private Entry<P,Q> get(P key) { //如果key都匹配直接返回当前value if (Objects.equals(key, this.key)) { return this; } //如果当前key不匹配则判断next节点是否为null,如果为null直接返回null if (Objects.isNull(this.next)) { return null; } //以上都不匹配就递归 return this.next.get(key); } /** * 必须实现Map.Entry<K,V>的方法 * 使用迭代器时会使用到 * @return */ @Override public P getKey() { return this.key; } @Override public Q getValue() { return this.value; } @Override public Q setValue(V value) { return (this.value = (Q) value); } /** * 因为使用的TreeSet集合所以需要实现Comparable的compareTo方法 * @param o * @return */ @Override public int compareTo(Entry<P, Q> o) { return (Objects.equals(this.key, o.key) && this.hash == o.hash) ? 0 : 1; }

测试代码


MyHashMap<String,String> map = new MyHashMap<>(); map.put("1","zhangsan1"); map.put("2","zhangsan2"); map.put("3","zhangsan3"); map.put("4","zhangsan4"); map.put("5","zhangsan5"); map.put("6","zhangsan6"); map.put("7","zhangsan7"); map.put("8","zhangsan8"); System.out.println(map.containsKey("100")); System.out.println(map.get("6")); System.out.println(map.isEmpty()); System.out.println(map.size()); System.out.println("========================"); /** * 使用iterator遍历 * */ Set<Map.Entry<String, String>> entries = map.entrySet(); Iterator<Map.Entry<String, String>> iterator = entries.iterator(); while (iterator.hasNext()) { Map.Entry<String,String> entry = iterator.next(); System.out.print(entry.getKey() + "\t"); System.out.println(entry.getValue() + "\t"); }

测试结果:


zhangsan1 zhangsan2 zhangsan3 zhangsan4 zhangsan5 zhangsan6 zhangsan7 zhangsan8

keySet()

返回此映射中所包含的键的 Set 视图。
这里使用了一个匿名内部类。


/** * 返回一个set类型,该方法使用了一个匿名内部类 * 并且重写了迭代器 * @return */ public Set<K> keySet(){ return new AbstractSet<K>() { @Override public Iterator<K> iterator() { return new Iterator<K>() { private Iterator<Map.Entry<K,V>> iterator = entrySet.iterator(); @Override public boolean hasNext() { return iterator.hasNext(); } @Override public K next() { return iterator.next().getKey(); } @Override public void remove() { iterator.remove(); } }; } /** * 数据的长度 * @return */ @Override public int size() { return size; } }; } //测试 MyHashMap<String,String> map = new MyHashMap<>(); map.put("1","zhangsan1"); map.put("2","zhangsan2"); map.put("3","zhangsan3"); map.put("4","zhangsan4"); map.put("5","zhangsan5"); map.put("6","zhangsan6"); map.put("7","zhangsan7"); map.put("8","zhangsan8"); /** * 使用iterator遍历 * */ Set<String> entries = map.keySet(); Iterator<String> iterator = entries.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + "\t"); } //结果 2 3 4 5 6 7 8

values()

返回此映射所包含的值的 Collection 视图。
这个方法与entrySet方法类似。需要一个集合 Collection 也需要在 put 时直接添加到集合中就好了。


/** * 仿造 values方法时使用,和仿造entryset方法原理一样 * 也是在put方法中直接将value存入即可. */ private Collection<V> list;

改造构造方法


/** * 有参构造 * @param defaultLength */ public MyHashMap(int defaultLength) { this.entries = new Entry[defaultLength]; //这里需要先实例化一个hashset集合 this.entrySet = new TreeSet<>(); //这里需要先实例化一个ArrayList this.list = new ArrayList<>(); }

在内部类和外部类的put方法中添加元素是加上一下代码,代码位置与entrySet.add的代码位置一样。


//仿造values方法,将value值直接储存到list集合中 this.list.add(entry.value); /** * 仿造这个方法也可以使用偷懒的方式了 * @return */ public Collection<V> values() { //在put的同时就储存了这个时候直接就返回了 return this.list; } //测试代码 MyHashMap<String,String> map = new MyHashMap<>(); map.put("1","zhangsan1"); map.put("2","zhangsan2"); map.put("3","zhangsan3"); map.put("4","zhangsan4"); map.put("5","zhangsan5"); map.put("6","zhangsan6"); map.put("7","zhangsan7"); map.put("8","zhangsan8"); /** * 使用iterator遍历 * */ Collection<String> entries = map.values(); Iterator<String> iterator = entries.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + "\t"); } //测试结果: zhangsan1 zhangsan2 zhangsan3 zhangsan4 zhangsan5 zhangsan6 zhangsan7 zhangsan8

containsValue(K value)

如果此映射将一个或多个键映射到指定值,则返回 true


/** * 如果此映射将一个或多个键映射到指定值,则返回 true。 * @param value * @return */ public boolean containsValue(V value) { return this.list.contains(value); } //测试代码 MyHashMap<String,String> map = new MyHashMap<>(); map.put("1","zhangsan1"); map.put("2","zhangsan2"); map.put("3","zhangsan3"); map.put("4","zhangsan4"); map.put("5","zhangsan5"); map.put("6","zhangsan6"); map.put("7","zhangsan7"); map.put("8","zhangsan8"); System.out.println(map.containsValue("zhangsan6")); 输出结果:true

MyHashMap源码


import java.util.*; /** * @author dcc * 自定义hashmap,暂时按照自己的思路写个最简单的HashMap,适合新手。 */ public class MyHashMap<K,V> { /** * 元素的总个数 */ private int size; /** * 数组默认长度 */ private static final int DEFAULT_LENGTH = 4; /** * 储存元素的数组 */ private Entry<K,V>[] entries; /** * 仿造entrySet方法需要定义一个set集合 */ private Set<Map.Entry<K,V>> entrySet; /** * 仿造 values方法时使用,和仿造entryset方法原理一样 * 也是在put方法中直接将value存入即可. */ private Collection<V> list; /** * 默认构造 */ public MyHashMap() { this(DEFAULT_LENGTH); } /** * 有参构造 * @param defaultLength */ public MyHashMap(int defaultLength) { this.entries = new Entry[defaultLength]; //这里需要先实例化一个hashset集合 this.entrySet = new TreeSet<>(); //这里需要先实例化一个ArrayList this.list = new ArrayList<>(); } /** * 返回此映射中的键-值映射关系数。 * 这个方法最简单了,直接定一个全局的size变量 * 然后直接在size方法中获取即可 * @return */ public int size() { return this.size; } /** * 判断是否有元素 * @return */ public boolean isEmpty() { return this.size > 0; } /** * 返回指定键所映射的值;如果对于该键来说,此映射不包含任何映射关系,则返回 null。 * @param key * @return */ public V get(K key) { int index = this.hash(key); if (Objects.isNull(this.entries[index])) { throw new NullPointerException("没有找到数据"); } //获取节点 Entry<K,V> entry = this.entries[index].get(key); return entry == null ? null : entry.value; } /** * 当需要put的时候,肯定就跟元素挂钩了 * 那么我们说过hashmap是数组+链表组成的。 * 现在第一步需要有一个数组了 * 首先在创建数组之前我们都知道hashmap是键(key)值(value)队的形式储存的 * 这个时候就需要创建一个储存key和value的类,这里使用内部类 * @param key * @param value * @return */ public V put(K key, V value) { /** * 创建需要添加的元素 */ Entry<K,V> entry = new Entry<>(key,value); /** * 添加元素之前需要有一个数组,那么需要在全局定一个内部类的数组 * 现在需要使用算法(key.hashcode()%entries.length)算出数据存在那个索引下。 */ int index = this.hash(key); /** * 判断数组该下标下是否有元素,如果有那么在判断是否key值一致 * 一致则覆盖,否则就添加 */ if (Objects.isNull(this.entries[index])) { //表示没有数据,可以直接保存 this.entries[index] = entry; //在put的时候顺带将entry插入到set中 this.entrySet.add(entry); //仿造values方法,将value值直接储存到list集合中 this.list.add(entry.value); this.size++;//这里表示新增一个元素 } else { //添加到链表了 this.entries[index].put(entry); } return value; } /** * 数组下标算法 * @param key * @return */ private int hash(K key) { return key.hashCode() % this.entries.length; } /** * 如果此映射包含对于指定键的映射关系,则返回 true。 * @param key * @return */ public boolean containsKey(K key) { int index = this.hash(key); return this.entries[index].get(key) != null; } /** * 如果此映射将一个或多个键映射到指定值,则返回 true。 * @param value * @return */ public boolean containsValue(V value) { return this.list.contains(value); } /** * 返回此映射所包含的映射关系的 Set 视图。 * @return */ public Set<Map.Entry<K,V>> entrySet() { return this.entrySet; } /** * 返回一个set类型,该方法使用了一个匿名内部类 * 并且重写了迭代器 * @return */ public Set<K> keySet(){ return new AbstractSet<K>() { @Override public Iterator<K> iterator() { return new Iterator<K>() { private Iterator<Map.Entry<K,V>> iterator = entrySet.iterator(); @Override public boolean hasNext() { return iterator.hasNext(); } @Override public K next() { return iterator.next().getKey(); } @Override public void remove() { iterator.remove(); } }; } /** * 数据的长度 * @return */ @Override public int size() { return size; } }; } /** * 仿造这个方法也可以使用偷懒的方式了 * @return */ public Collection<V> values() { //在put的同时就储存了这个时候直接就返回了 return this.list; } /** * 这是一个成员内部类 * 储存hashmap元素的key和value * 要仿造entrySet方法需要实现 Comparable, Map.Entry<K,V> */ private final class Entry<P extends K,Q extends V> implements Comparable<Entry<P,Q>>, Map.Entry<K,V> { /** * key 键 */ private P key; /** * value 值 */ private Q value; /** * hash码,比较key是否重复使用 */ private long hash; /** * 数组+链表,所以就需要提供下个节点 */ private Entry<P,Q> next; /** * 构造器 * @param key * @param value */ private Entry(P key, Q value) { this.key = key; this.value = value; this.hash = this.key.hashCode(); } /** * 新增 * @param entry */ private void put(Entry<P,Q> entry) { /** * 表示已经有了那么需要判断key是否一致 */ if (Objects.equals(this.key, entry.key) && this.hash == entry.hash) { //表示一致直接替换value值即可 this.value = entry.value; } else {//表示可以新增了 /** * 如果next中没有元素直接赋值了 */ if (Objects.isNull(this.next)) { this.next = entry; //在put的时候顺带将entry添加到set中 MyHashMap.this.entrySet.add(entry); //仿造values方法,将value值直接储存到list集合中 MyHashMap.this.list.add(entry.value); size++;//这里也表示为新增一个元素 } else {//递归 this.next.put(entry); } } } /** * 获取数据 * @param key * @return */ private Entry<P,Q> get(P key) { //如果key都匹配直接返回当前value if (Objects.equals(key, this.key)) { return this; } //如果当前key不匹配则判断next节点是否为null,如果为null直接返回null if (Objects.isNull(this.next)) { return null; } //以上都不匹配就递归 return this.next.get(key); } /** * 必须实现Map.Entry<K,V>的方法 * 使用迭代器时会使用到 * @return */ @Override public P getKey() { return this.key; } @Override public Q getValue() { return this.value; } @Override public Q setValue(V value) { return (this.value = (Q) value); } /** * 因为使用的TreeSet集合所以需要实现Comparable的compareTo方法 * @param o * @return */ @Override public int compareTo(Entry<P, Q> o) { return (Objects.equals(this.key, o.key) && this.hash == o.hash) ? 0 : 1; } } }

备注

以上都是 HashMap 的方法基本上都模仿玩了还有些继承的方法就不写了,以上可能不是完全按照jdk的源码做的。

主要是让广大初学者知道 hashmap 的原理是数组+链表实现的就足够了,好了集合就写到这里了,其它的集合基本上用法都很类似,大家根据api来一个个测试就差不多会使用了。

写完了如果写得有什么问题,希望读者能够给小编留言,也可以点击[此处扫下面二维码关注微信公众号](https://www.ycbbs.vip/?p=28 "此处扫下面二维码关注微信公众号")

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:055-五十五、Java之手写HashMap(下)

链接:https://www.javajike.com/article/1362.html

« 056-五十六、Java之Properties及对象序列化
054-五十四、Java之手写HashMap(上)»

相关推荐

QR code