hashmap查找与hashcode

Map map=new HashMap();
String s1=new String("AA");
String s3=new String("AA");
String s4="AA";
String s6="AA";
map.put(s1,"Value");
String s2=(String)map.get(s3);
String s5=(String)map.get(s4);
s1==s3 false   s4==s6 true //这里的==比较的应该不是hashcode吧
s2,s5都可以得到值Value

这里以下是查找key是否存在Entry[] table中
if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
1: hashcode的API上解释是 将该对象的内部地址转换成一个整数来实现的。这里的内部地址是该对象在堆中的地址还是对象的引用存储在栈中的地址计算出来的?
2: java中可以输出一个对象在堆中的地址吗?在同一个JVM进程中是否有可能不同的对象的引用输出相同的hashcode呢?
3:为什么s1,s3,s4的hashcode都是相同的在我机子上是2080。不是说s1,s3的引用是指向堆中的对象的实例吗?s4是方法区中得字符串常量池?这里的hashcode是引用本身存储在栈中的地址呢还是其指向的对象在堆中的地址?
4 :s1==s3 是比较哪个地址呢?
5:hashMap中查找key时 int hash = hash(key.hashCode());
不同的key经过hash()运算是否有可能的到相同的hash呢?
e.hash == hash && ((k = e.key) == key || key.equals(k))这里一定要比较2个hash值相等吗?为什么

回答: hashmap查找与hashcode

  1. 1,当然是对象在堆中的地址,因为引用可有很多,如果是引用的地址的话,那一个对象有多少个引用就有多少个hashcode,显然不对;
    2,对象地址是无法直接获取的,你拿了也没用,但是可以获得任何对象的hashcode,不是对象重载了hashCode()方法以后的,而是原生的:System.identityHashCode(Object x);
      通过System.identityHashCode出来的任何不同的对象的HashCode都是不同的,你通过Object.hashCode()返回的值发现不同的对象这个值相同是因为对象覆写了hashCode()方法。
    3,s1,s2,s3的hashcode相同是因为String类覆写了hashCode()方法,你看看源码就知道String的hahsCode只和String的内容(char[] value)有关,
    另外的解释是:他们相互equals返回true,所以hashCode()也应该相等();
    当然,System.identityHashCode(s1)与System.identityHashCode(s2)就不想等了。
    4,s1==s3比较的是System.identityHashCode(s1)和System.identityHashCode(s3)

hashmap 判断键的相等依据是什么?equals()?hashcode()?==?

  1. Q
    package collection;
      
    import java.util.HashMap; 
    import java.util.Map; 
     
    public class Test2 { 
      
         /**
          * @param args
          */ 
         public static void main(String[] args) { 
             // TODO Auto-generated method stub 
             Map map=new HashMap(); 
             map.put(new PhoneNumber(020,1234567),"xx"); 
             System.out.println(map.get(new PhoneNumber(020,1234567))); 
        } 
      
         private static class PhoneNumber{ 
             /**
              * @param areaCode
              * @param extension
              */ 
             public PhoneNumber(int areaCode, int extension) { 
                 this.areaCode =(short) areaCode; 
                 this.extension = (short)extension; 
             } 
      
             private short areaCode; 
             private short extension; 
              
             public boolean equals(Object o){ 
           
                 if(o==this){ 
                     return true; 
                 } 
                 if(!(o instanceof PhoneNumber)){ 
                     return false; 
                 } 
             PhoneNumber pn=(PhoneNumber)o; 
             return pn.extension==extension && pn.areaCode==areaCode; 
             } 
             //result就是我们得到的散列值,,计算过程有多种,这里只是个例子 
             public int hashCode(){ 
                 int result=17; 
                 result=37*result+areaCode; 
                 result=37*result+extension; 
                 return result; 
             } 
              
         } 
          
    } //结果是xx,就是查处了这个对象
    ======================================================================
    ======================================================================
    ======================================================================

    上述的这段代码中,判断hashmap的键相等,使用了equals方法,但是equals方法又重写了,使用的是==判断。
    我的问题是
    1----hashcode()方法在hashmap中哪里有调用?或者用处是什么???
    2----  "=="是判断栈中的引用是不是指向同一个堆中的对象,但map.get方法中是new了一个键值对象,就是说,指向的不是同一个键值对象,结果居然查到了,就是说,它们指向同一个对象!!!为什么??????
    3----是不是所有hash有关的类,要比较相等,都要重写hashcode方法???
    4----总结下我的问题,其实就是hashmap中   equals()   hashcode()   ==  这三者用处各是什么,哪里用的到?????????
  2. A
    回答如下
    1.hashcode这个方法是用来鉴定2个对象是否相等的,在hashmap中,由于key是不可以重复的,他在判断key是不是重复的时候就判断了hashcode这个方法,而且也用到了equals方法。这里不可以重复是说equals和hashcode只要有一个不等就可以了!所以简单来讲,hashcode相当于是一个对象的编码,就好像文件中的md5,他和equals不同就在于他返回的是int型的,比较起来不直观。我们一般在覆盖equals的同时也要覆盖hashcode,让他们的逻辑一致。举个例子,如果姓名和性别相等就算2个对象相等的话,那么hashcode的方法也要返回姓名的hashcode值加上性别的hashcode值,这样从逻辑上,他们就一致了。
    2.你 new 出来的PhoneNumber对象是做为map的key 根据上面的1可以得到你获取的就是刚刚保存的key的值 这仅仅是在map对象中 ,实际中他们是不同的对象
    3.根据1,可以自己判断
    4.==号是值的比较 对于原始类型就是值的比较,对于引用类型就是引用地址的直接比较,‘==’在map中 没啥用 map只会调用equals方法比较

c++hashmap里能否重写判断hashcode是否相等的函数吗?代码如下

  1. Q
    个人理解每个对象分配一个hashcode,先判断是否相等,相等的话再执行比较函数,不相等就不会执行比较函数了。我能否自己写判断hashcode是否相等的方法,让我想要的对象执行比较函数。
    这里我是想在在一个保存坐标的数组里找出所有坐标值相差距离小于3的点集,如(220,119),(220,220),(119,220)是属于一个点集,
    判断依据是abs(a.x - b.x) + abs(a.y - b.y) < 3(a,b是点坐标),每一个元素和其他元素各自进行比较,然后保存点集
    在这程序里我想通过判断hashcode是否相等来找点集,相等依据就是abs(a.x - b.x) + abs(a.y - b.y) < 3,但是hashmap默认相同的对象才有相同的hashcode,所以我没办法,只能让所有点拥有相同的hashcode,就是1,然后进入比较函数里进行点比较,但这样效率太低,比较函数效率远远低于hash函数里判断hashcode是否相等,所有我想问是否能重写判断hashcode相等的函数方法。
    如果不能,我还有什么方法可以实现我的功能,这里考虑点坐标有上万个,之前我用的是嵌套for循环,点坐标两两比较,能实现但是效率太低,别人让我试试hashmap,然后我就碰到这种问题了,hashmap找相同的元素的确可以实现,但是像我这样,一定范围里的点也当作相等的,不知道怎么做了

    #include <opencv2/core/core.hpp>
    #include <opencv2/imgproc/imgproc.hpp>
    #include <opencv2/highgui/highgui.hpp>
    #include <iostream>
    #include <math.h>
    #include <string>

    using std::string;
    #include <unordered_map>
    using std::unordered_multimap;
    using namespace std;
    using namespace cv;

    class StrHash{
    public:
    size_t operator()(const Point a) const {

    return 1;
    }
    };

    class StrCompare{
    public:
    bool operator()(const Point& a, const Point& b) const {

    if (abs(a.x - b.x) + abs(a.y - b.y) < 3) {
    return true;
    }
    else
    return false;
    }

    };

    int main()
    {
    unordered_multimap<Point, int, StrHash, StrCompare> map;
    map.insert(make_pair(Point(30, 120), 1));
    map.insert(make_pair(Point(220, 120), 2));
    map.insert(make_pair(Point(220, 120), 3));
    map.insert(make_pair(Point(220, 120), 4));
    map.insert(make_pair(Point(220, 119), 5));
    map.insert(make_pair(Point(30, 120), 6));
    unordered_multimap<Point, int, StrCompare>::iterator iter1;
    unordered_multimap<Point, int, StrCompare>::iterator iter2;
    for (iter1 = map.begin(); iter1 != map.end();)//遍历
    {
    int num = map.count((*iter1).first);
    iter2 = map.find((*iter1).first);
    if (num > 2) {
    for (int i = 1; i <= num; i++)
    {
    cout << (*iter2).first << "  " << i << endl;
    iter2++;
    }
    iter1++;
    }
    else {

    iter1++;

    }

    }

    }
  2. A
    当你确定要修改的语句时,直接修改原始文件,重建所有即可。

    谢谢赵老师回答,但是可以直接修改源码吗,如果修改源码,我下次再新建一个项目再调用到这个源码,我不就变成上次的功能了,或者说别人导入我的项目,也不能正常运行吧,他的源码没有改,请指导一下,谢谢

重写hashcode()方法后,HashMap变成升序?

  1. Q
    public class ObjTest{

    private Integer id;

    public boolean equals(Object obj) {
    if(obj instanceof ObjTest) {
    ObjTest ojb = (ObjTest) obj;
    if(this.id.intValue() == ojb.id.intValue()) {
    return true;
    }
    }
    return false;
    }

    public int hashCode() {
    return id;
    }

    public Integer getId() {
    return id;
    }

    public void setId(Integer id) {
    this.id = id;
    }
    }

    public class HashMapTest {

    private static Map<ObjTest, Integer> map = new HashMap<ObjTest, Integer>();

    private static void init() {
    ObjTest obj1 = new ObjTest();
    obj1.setId(3);
    ObjTest obj2 = new ObjTest();
    obj2.setId(2);
    ObjTest obj3 = new ObjTest();
    obj3.setId(1);

    map.put(obj1, 3);
    map.put(obj2, 2);
    map.put(obj3, 1);

    for(Map.Entry<ObjTest, Integer> e : map.entrySet()) {
    ObjTest obj = (ObjTest) e.getKey();
    System.out.println("key:" + obj.getId());
    }
    }


    public static void main(String[] args) {
    init();
    }
    }

    结果:
    key:1
    key:2
    key:3

    求解?
  2. A
    你为什么要关心hashmap遍历元素时的顺序呢?
    它之所以在这里是升序,完全是因为你改变了hashmap在进行散列是否的逻辑,当你把ObjTest id得值取其他很大的时候,就不一定是升序的了

    关于hashmap进行hash的过程可以参考以下文章:
    http://www.ibm.com/developerworks/cn/java/j-lo-hash/?ca=dgr-cn-javaeye0912

hashcode有什么作用?一般面试都问hashMap,hashTable区别。该怎么回答?

  1. Q
    hashcode()是Obeject的一个方法。每个子类都有,应该是很重要的一个方法,那么hashcode()到底是什么东西,干什么用的。hashMap,hashTable什么区别面试常题,实际很少遇到。到底在生产中什么情况会需要考虑到这两者的区别。请大神们指点。
  2. A
    hashcode()到底是什么东西  :::其实是一串数字(对象的内存地址),就是指针了。。
    主要用来比对俩个对象是不是同一个。。
    HashMap不是线程安全的,Hashtable是线程安全的

关于java hashcode方法对性能影响的一些疑问

  1. Q
    java api中关于hashcode的规定,就是两个值相等,他们的hashcode一定相等,但hashcode相等,其对应的值不一定相等,说hashcode相等会影响hashtables性能,具体怎么影响性能的。
  2. A
    最好的办法是去阅读HashMap或者Hashtable的代码(二者的实现是比较接近的),或者研究一下数据结构里面讲述的Hash表的数据结构,HashMap&Hashtable是通过拉链法来构造的。 检索的时候使用HashCode作为Hash算法的Key,当多个HashCode相同时,需要逐个调用equals方法来查找。

    极端情况下,如果所有的对象HashCode都相同,则检索复杂度为O(n),如果Hash后所有的对象的Hash编码都不同(不同HashCode的Hash结果也有可能是相同的),则检索复杂度为O(1)

hashtabe,hashmap,等为什么要用hash算法

  1. Q
    如果是为了2分查找算法,生成一个整数, 好做排序的话, 那么每个字符实际上都对应一个assiic码值

    比如
    ac = 6163
    bb = 6262
    因此就算不用hash散列算法 也不会重复呀. 更何况,hash算法也不能保证不发生碰撞.  这个情况下, 为什么还要使用hash呢???  求明白的给个原因
  2. A

    我都说了 我知道2分查找算法啊... 你还说什么 只需一次比较...何况这也不是所谓一次比较就能得出.

    求明白人给个回复


    说实话实在不想回这个贴,不管别人说的对不对你这个态度就有问题
    根据实际情况找到合适的散列函数分配足够的空间,一次比较找到是有可能实现的
    看数据结构散列这一章

    好吧, 我态度有问题, 表示歉意.
    我明白 hashmap.get(hashcode) 就是直接从数组里端出来,没有循环(不冲突的情况)
    我在C#区也发了个贴:


    我其实就是不明白为什么要用hash算法算出个那么大的值来.   那样的话[key的hash最小值]-->[key的hash最大值]是很恐怖的.  这样的话要耗费多少内存来生成这么个数组呢?
    key的hash值也不是直接拿来当数组下标用的
    下面hashMap的一段代码

     public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e.value;
            }
            return null;
        }

    看table这个数组下标,是indexFor(hash, table.length)
    下面是indexFor方法

    static int indexFor(int h, int length) {
            return h & (length-1);
        }

在重写了对象的equals方法后,还需要重写hashCode方法吗?

  1. Q
    RT:
    在重写了对象的equals方法后,还需要重写hashCode方法吗
    最近在看集合,对此有疑问,请高手回答。在重写了对象的equals方法后,还需要重写hashCode方法吗?
  2. A
    我比较同意walsh的说法:

    首先说建议的情况:  比如你的对象想放到Set集合或者是想作为Map的key时(非散列的Set和Map,例如TreeSet,TreeMap等),那么你必须重写equals()方法,这样才能保证唯一性。当然,在这种情况下,你不想重写hashCode()方法,也没有错。但是,对于良好的编程风格而言,你应该在重写equals()方法的同时,也重写hashCode()方法。

    然后再说说必须重写hashCode()的情况:
        如果你的对象想放进散列存储的集合中(比如:HashSet,LinkedHashSet)或者想作为散列Map(例如:HashMap,LinkedHashMap等等)的Key时,在重写equals()方法的同时,必须重写hashCode()方法。

    这里我想给楼主讲讲sun的设计者为什么需要设计hashcode方法,也许这样你就应该知道什么时候该重写它了。
    数据结构有一种为了提高查找的效率而存在的数据结构——散列表,散列表其实是普通数组概念的推广,因为可以对数组进行直接寻址,故可以再O(1)时间内访问数组的任意元素,thinking in java中有个对hashmap简单的实现,我们来看看你就明白了:
    //: containers/SimpleHashMap.java
    // A demonstration hashed Map.
    import java.util.*;
    import net.mindview.util.*;
    
    public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
      // Choose a prime number for the hash table
      // size, to achieve a uniform distribution:
      static final int SIZE = 997;
      // You can't have a physical array of generics,
      // but you can upcast to one:
      @SuppressWarnings("unchecked")
      LinkedList<MapEntry<K,V>>[] buckets =
        new LinkedList[SIZE];[color=red]//List数组里每项是个List,数组下标是hashcode方法的返回值再经过散列函数得到的,相当于散列表的关键字,它亦代表着每个对象的关键字。(不能显示new一个泛型数组,但是你可以new一个泛型数组的引用,如有需要以后可以将普通数组转型为泛型数组)。[/color]
      public V put(K key, V value) {[color=red]//将这个对键值放进hashmap中。[/color]
        V oldValue = null;
        int index = Math.abs(key.hashCode()) % SIZE;[color=red]//这里就是通过散列函数对hashcode的返回值处理得到一个关键字,它代表了对象在数组里的位置,既是数组下标。[/color]
        if(buckets[index] == null)
          buckets[index] = new LinkedList<MapEntry<K,V>>();[color=red]//如果是第一次散列到这个数组下标,那么就新生成一个LinkedList,可以看到它里面保存的是MapEntry<K,V>键和值。[/color]
        LinkedList<MapEntry<K,V>> bucket = buckets[index];[color=red]//将这个LinkedList赋值给一个bucket(桶),以后就直接在这个bucket进行操作。[/color]
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        while(it.hasNext()) {
          MapEntry<K,V> iPair = it.next();
          if(iPair.getKey().equals(key)) {[color=red]//如果已经存在同一个键值,那么就更新value。[/color]
            oldValue = iPair.getValue();
            it.set(pair); // Replace old with new
            found = true;
            break;
          }
        }
        if(!found)
          buckets[index].add(pair);[color=red]//如果是一个新的键值,那么直接添加到这个LinkedList中。[/color]
        return oldValue;
      }
      public V get(Object key) {[color=red]//看hashmap是如何凭借hashcode方法快速定位到键值。[/color]
        int index = Math.abs(key.hashCode()) % SIZE;[color=red]//与put方法中的作用一样,生成数组下标,因为我存的时候就是存到这个地方的,那么我取的时候直接访问buckets[index]。[/color]
        if(buckets[index] == null) return null;[color=red]//直接访问这个数组下标的LinkedList,如果为null,则返回。[/color]
        for(MapEntry<K,V> iPair : buckets[index])[color=red]//为什么要用LinkedList,因为hashcode方法产生的散列码不能完全确定一个对象,也就是说会和其他对象发生“碰撞”,即散列到同一个数组下标,解决这个问题的组号办法就是定义一个List把它们保存起来,但是在这个List中,我们必须保证能用equals方法确定对象的身份,这也就是为什么很多人说hashcode()相等,equals()不一定相等,而equals()相等的两个对象,hashcode()一定相等。所以这里要直接在LinkedList执行线性查找。[/color]
          if(iPair.getKey().equals(key))
            return iPair.getValue();
        return null;
      }
      public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
          if(bucket == null) continue;
          for(MapEntry<K,V> mpair : bucket)
            set.add(mpair);
        }
        return set;
      }
      public static void main(String[] args) {
        SimpleHashMap<String,String> m =
          new SimpleHashMap<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
      }
    } /* Output:
    {CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa}
    Asmara
    [CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa]
    *///:~
    
    

    怎样?现在应该知道hashcode方法的作用了吧,它就是用来提高效率的,有句话说得好:为速度而散列。因为散列的Set和Map是基于hashcode方法来查找对象的,所以你在使用这些类的时候一定要覆盖hashcode方法,而非散列的Set和Map,例如TreeSet,TreeMap等,它们只需equals方法就可以唯一确定对象的身份。这样说,想必已经很清楚了吧。

hashmap 中的Entry链问题

  1. Q
       引用网上的一段话:引用当程序试图将一个key-value对放入HashMap中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部

    我的疑问是,这段话要怎么理解
    因为当我定义
    map.put(1,"a");
    map.put(1,"b");
    


    此时map的size实际是1,map.get(1)为b也就是说后put的元素把前面的覆盖了。
    所以我想知道的是这个Entry里有多个元素,该怎么理解?
  2. A
    entry应该指的就是键值对吧

10000个对象放入hashtable,hashcode不同?为什么?

  1. Q
    10000个对象放入hashtable,hashcode不同?为什么?
  2. A
    1. 如果要一样的会出现什么问题呢?
    答: 如果一个collection,比如hashmap中存储了一千个对象,那么如何判断互相之间不相等呢,如果一个一个比较那么得比较 1000!次,所以根据获取hash的方式来指定一个不会重复的值。

    2. hash值怎么得来。
    答:是通过hash算法,也就是散列算法。哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。可以这样简单理解,hashCode方法实际上返回的就是对象存储位置的映像。