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

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

青川网站制作公司哪家好,找成都创新互联公司!从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作,到程序开发,运营维护。成都创新互联公司从2013年成立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司

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

  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的工作原理及实现方法是什么”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注创新互联行业资讯频道。


网页标题:Java中​HashMap的工作原理及实现方法是什么
文章分享:http://myzitong.com/article/pgdcdd.html