<Other> 关于哈希算法

前言

  做应用层的人,一提到算法和数据结构就感觉很难,很高深,我以前也是这样,现在当然还是这样。大学的时候,毕设的课题就是地图匹配算法,那时候哪懂这些,基本就是老师说一点,然后写一点,要不就是网上论文找来找去,根本不知道自己在干什么。

Hash算法

  其实就算做web引用,也需要了解一些算法。

  我们都知道Object类带有一个hashCode的方法,但是没有给实现,技术分享,一般来说我从来不会用到这个方法,也基本不会去重写这个方法,那这个方法用来干什么的呢?

  hashcode是用来提高查找元素效率的!为什么?

  map是一个非常常用的数据结构,但是如果在放在内存中随意存放的话,查找的时候非常麻烦,所以我们利用hash表来整理归类这些数据,具体这样做:

  1.将对象通过hash算法生成一个2^32范围内的int值,然后根据一个因子(一把来说是表的长度)来取模,将2^32范围内的hash压缩到因子大小。并存入表(其实是一个数组)中,这个表就叫哈希表。

  2.查找该值的时候,直接取查找的key的哈希值hk,然后arr[hk]就能直接找到了,如果不考虑hash冲突的情况,时间复杂度是O(1),如果有n个冲突,复杂度就是O(n)。

  3.这种方法的代价是需要申请内存来维护一个哈希表,以及每次添加获取的时候需要经过hash算法,但这些代价都是值得的。

  哈希冲突,这个问题有四种解决办法,这里不作详细讨论,可以记住的是HashMap中,用的是链地址法。

  hashcode有一个很重要的特性,两个对象的hashcode相等,两个对象不一定相等,而两个对象相等,则它们的hashcode一定相等。

  怎么理解这一点呢,比如,有一个类持有wage和cost两个变量,我们重写它的hashcode方法,返回值为wage-cost。现在有两个对象,A对象:wage:5000,cost:3000,B对象:wage:4000,cost2000,那么他们的hashcode是不是就一样了,而这两个对象明显是不一样的。而两个对象一样(equals为true),那么它们的hashcode就一定一样的。

  这里就牵扯到equals()方法,首先我们搞清楚equals和==的区别,前者是说两个对象一样,就想好双胞胎,后者说的是两个是同一个对象,就好像是同一个人。

                    技术分享

  这是String类的equals方法,那么首先它来判断两个对象是不是同一个,如果是,直接返回true。否则继续判断是否是相同类型,如果一个是人一个是狗就不用再比较下去了,然后再判断内在的东西是否相同(比如这里的String就比较长度啦,每一个具体的char啦)。从这里我们可以总结出来,equals()判断的三个流程:

    1.==:判断内存地址

    2.instanceof:判断类型

    3.具体成员判断:比如说前面提到的那个类,就比较cost和wage。

  什么时候需要我自己重写hashcode呢,就是你的类需要作为key放到以hash为基础的容器(hashmap、hashset、hashtable等)里面的时候。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。