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的工作原理及實現方法是什么”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。