Java中​HashMap的工作原理及实现方法是什么

今天小编给大家分享一下Java中HashMap的工作原理及实现方法是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

HashMap的工作原理及实现

1．  如何实现一个Map

1.1  与Map相关的知识

1.1.1  Map.Entry接口

一个实现了Map.Entry接口的类代表的是一个Map中的条目（一个key-value　pair）。所以一个Map中必须要有一个实现了Map.Entry接口的类，并用这个类来存放Map中的key-value　pair。

1.1.2  public abstract Set entrySet()函数

1)  entrySet()函数返回一个Set，并且Set中的每一个元素都是一个Map.Entry类型的对象。在entrySet()函数中要把Map中所有的key-value　pair以Map.Entry封装后存入Set中的。

2)  当对Map进行修改操作后，entrySet()函数都会被调用。所以对Map的修改也会产生对这个Set的修改。

3)  当用这个Set的iterator进行操作时，不能进行add和addAll的操作。

1.2  实现一个简单的Map的实例

import Java.util.*;

/**XML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

 * MPair类实现了Map.Entry

 */

class MPair

  implements Map.Entry, Comparable{

  object key, value; //key和value分别用来存放Map中的key和value

  MPair(Object k, Object v){

  key = k;

  value = v;

}

//下面方法实现了Map.Entry接口中的方法

  public Object getKey() { return key; }

  public Object getValue() { return value; }

  public Object setValue(Object v){

  Object result = value;

  value = v;

  return result;

}

//下面方法实现了Comparable接口中的方法

  public boolean equals(Object o){

  return key.equals(((MPair)o).key);

  }

  public int compareTo(Object rv){

  return ((Comparable)key).compareTo(((MPair)rv).key);

  }

}

class SlowMap extends AbstractMap{

  private ArrayList

  keys = new ArrayList(),

  values = new ArrayList();

  public Object put(Object key, Object value){

  Object result = get(key);

  if(!keys.contains(key)){ //（1）

  keys.add(key);

  values.add(value);

  }

  else

  values.set(keys.indexOf(key), value);

  return result;

  }

  public Object get(Object key){

  if(!keys.contains(key)){

  return null;

  }

  else

  return values.get(keys.indexOf(key));

}

//用Mpair封装Map中的key-value　pair并存入Set中

  public Set entrySet(){

  Set entries = new HashSet();

  Iterator

  ki = keys.iterator(),

  vi = values.iterator();

  while(ki.hasNext())

  entries.add(new MPair(ki.next(), vi.next()));

  return entries;

  }

}

public class ExplicitStatic{ 

  public static void main(String[] args){

  SlowMap m = new SlowMap();

  for( int i=1; i<10; i++)

  m.put("km" + i, "m" + i);

  System.out.println(m); 

  }

}

  在上面代码的（1）处，我们要从ArrayList中查找出是否具有key值，而这个查找过程线性查找，且key不具任何顺序，所以速度会很慢。

1.3  如何对Map用迭代器进行操作

其它容器可以通过iterator()函数来生成对象的迭代器，但Map是不能生成的。如果要用迭代器对Map进行操作，则要通过entrySet()函数。用entrySet()函数生成的迭代器不能对Map进行add和addAll的操作。

  public class ExplicitStatic{ 

  public static void main(String[] args){ 

  HashMap m = new HashMap();

  for( int i=1; i<10; i++)

  m.put("km" + i, "m" + i);

  System.out.println("User for loop：");

  for( int i=1; i<=m.size(); i++ )

  System.out.println("km" + i + " = " + m.get("km" + i));

  System.out.println("User Iterator loop：");

  Iterator it = m.entrySet().iterator();

  while(it.hasNext()){

  Map.Entry entry = (Map.Entry)it.next();

  System.out.println(entry.getKey() + " = " + entry.getValue());

  }

  }

}

2．  与HashMap相关的几个函数

1)  hashCode()函数

Object.hashCode()函数会为对象产生hash code。如果一个类没有实现hashCode()函数，那么在缺省情况下将返回它的对象的内存地址。

2)  equals()函数

Object.equals()在比较两个对象时，比较的是两个对象的内存地址。

3．  HashMap的工作原理

3.1  用array来表现key的信息。每个key的hashCode()函数会为key产生一个hash　code，而key的hash 　code作为array的索引。如假设有一个名为bucket的arrsy，姥一个hash　code为2的key就被索引到bucket[2]，key所对应的值也在bucket[2]中。

3.1  由于array中存放的是value值，而HashMap的元素个数可以是无限的，所以array中的元素指向的不是某个key的value，而是指向具有相同的hash　code的key的value值（也就是说指向的是一串values值）。如假设array被定义为LinkedList []bucket = new LinkedList[10]，那么bucket[2]中存放的是所有hash　code值为2的key的value。

4．  自己实现一个简单的HashMap及其原理

4.1  在put()方法中：

1)  首先通过key得出要插入的key-value　pair的hash　code，并这个hash　code作为索引在数组bucket中找出key所对应的元素。

2)  把要插入的key-value　pair封装成实现了Map.Entry接口的类的一个对象。

3)  在操作1）所找出的数组元素（也是一个LinkedList）中查看是否有与要插入的key-value　pair的key相同的元素，如果有，则对之进行更新；如果无，则把要插入的key-value　pair数组元素中。

4.2  在get()方法中

1)  首先通过key得出要查找的key-value　pair的hash　code，并这个hash　code作为索引在数组bucket中找出key所对应的元素。

2)  把要查找的key-value　pair的key封装成实现了Map.Entry接口的类的一个对象。

3)  在操作1）所找出的数组元素（也是一个LinkedList）中查看是否有与要插入的key-value　pair的key相同的元素，如果有，则返回key所对应的value；如果无，则返回一个null。

4.3  一个实例

import java.util.*;

/**

 * MPair类实现了Map.Entry

 */

class MPair

  implements Map.Entry, Comparable{

  Object key, value;

  MPair(Object k, Object v){

  key = k;

  value = v;

  }

  public Object getKey() { return key; }

  public Object getValue() { return value; }

  public Object setValue(Object v){

  Object result = value;

  value = v;

  return result;

}

    /**

       * 当比较两个MPair对象时，比较的是它们的key值

       */

  public boolean equals(Object o){

  return key.equals(((MPair)o).key);

  }

  public int compareTo(Object rv){

  return (((Comparable)key).compareTo(((MPair)rv).key));

  }

}

class SimpleHashMap extends AbstractMap{

  private final static int SZ = 997;

  private LinkedList[] bucket = new LinkedList[SZ];

  /**

  * 把key和value封装成Map.Entry的实现类后插入到array中

  */

  public Object put(Object key, Object value){

  Object result = null;

  //通过key得到要插入的key-value　pair的hash　code

  int index = key.hashCode() % SZ;

  if(index < 0) index = - index;

  if(bucket[index] == null)

  bucket[index] = new LinkedList();

  //通过hash　code找出要插入的key所对应的array中的元素

  LinkedList pairs = bucket[index];

  //把要插入的key-value　pair封装成MPair

  MPair pair = new MPair(key, value);

   ListIterator it = pairs.listIterator();

  boolean found = false;

  //检查是否有与要插入的key相同的key存在，如果有，就对之进行更新

  while(it.hasNext()){

  Object iPair = it.next();

  if(iPair.equals(iPair)){

  result = ((MPair)iPair).getValue();

  it.set(pair);

  found = true;

  break;

  }

  }

  //如果无，则把新的key-value　pair插入

  if(!found)

  bucket[index].add(pair);

  return result;

  }

  public Object get(Object key){

  int index = key.hashCode() % SZ;

  if(index < 0) index = -index;

  if(bucket[index] == null) return null;

  LinkedList pairs = bucket[index];

  ListIterator it = pairs.listIterator();

  MPair match = new MPair(key, null);

  while(it.hasNext()){

  Object iPair = it.next();

  if(iPair.equals(match))

  return ((MPair)iPair).getValue(); 

  }

  return null;

  }

  public Set entrySet(){

  Set entries = new HashSet();

  for(int i=0; i<bucket.length; i++){

  if(bucket[i] == null) continue;

  Iterator it = bucket[i].iterator();

  while(it.hasNext())

  entries.add(it.next());

  }

  return entries;

  }

}

public class ExplicitStatic{ 

  public static void main(String[] args){ 

  SimpleHashMap m = new SimpleHashMap();

  for( int i=1; i<10; i++)

  m.put("km" + i, "m" + i);

  System.out.println(m);

  }

}

以上就是“Java中HashMap的工作原理及实现方法是什么”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。