正文

Java之手写HashMap(下)

toobug
toobugV管理员/3.98 W阅读/0评论
0612
此篇文章发布距今已超过2865天，您需要注意文章的内容或图片是否可用！

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<Map.Entry<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");
}


测试结果：

1  zhangsan1  
2  zhangsan2  
3  zhangsan3  
4  zhangsan4  
5  zhangsan5  
6  zhangsan6  
7  zhangsan7  
8  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");
}

//结果

1  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来一个个测试就差不多会使用了。


本文标题：Java之手写HashMap(下)
本文链接：https://blog.quwenai.cn/post/474.html
作者授权：除特别说明外，本文由 toobug 原创编译并授权 TOOBUG信息安全网 刊载发布。
版权声明：本文不使用任何协议授权，您可以任何形式自由转载或使用。

本文链接：https://blog.quwenai.cn/post/474.html 

分享到：
本站所有内容均来自于互联网收集及用户投稿,如果想系统学习相关知识 建议在本博客【自学成才】栏目选择合适的课程进行系统化学习
-- 展开阅读全文 --