[转帖]跟我一起阅读Java源代码之HashMap(一)_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3457 | 回复: 0   主题: [转帖]跟我一起阅读Java源代码之HashMap(一)        下一篇 
jxxs_12
注册用户
等级:下士
经验:190
发帖:14
精华:0
注册:2013-1-15
状态:离线
发送短消息息给jxxs_12 加好友    发送短消息息给jxxs_12 发消息
发表于: IP:您无权察看 2013-1-15 14:30:06 | [全部帖] [楼主帖] 楼主

最近闲的很,想和大家一起学习并讨论下Java的一些源代码以及其实现的数据结构,

不是什么高水平的东西,有兴趣的随便看看

1. 为什么要用Map,以HashMap为例

           很多时候我们有这样的需求,我们需要将数据成键值对的方式存储起来,根据key来获取value(value可以是简单值,也可以是自定义对象)

       当然用对象数组也能实现这个目的,查找时可以遍历数组,比较关键字来获取对应的value

       从性能上来讲,遍历大数组会消耗性能

       从API易用性来讲,需要自己实现查找的逻辑

       所以用HashMap是必要的    

2. HashMap的数据结构是怎么样的

       我一直对HashMap的内部结构很好奇,看了源码之后发现他是用散列实现的,即基于hashcode

       大体思想是这样的

    (1). 首先建立一个数组用来存取数据,假设我们定义一个Object[] table用来存取map的value

这个很容易理解,key存在哪里呢?暂时我不想存储key

       (2). 获得key的hashcode经过一定算法转成一个整数

           index,这个index的取值范围必须是0=<index<table.length,然后我将其作为数组元素的下标

           比如执行这样的操作:table[index] = value;

           这样存储的问题解决了

       (3). 如何通过key去获取这个value呢

           这个太简单了,首先获取key的hashcode,然后通过刚才一样的算法得出元素下标index

           然后value = table[index]

简单的HashTable实现如下

Java代码
北京联动北方科技有限公司北京联动北方科技有限公司北京联动北方科技有限公司

  1. public class SimpleHashMap { 
  2.       
  3.        private Object[] table; 
  4.       
  5.        public SimpleHashMap() { 
  6.              table = new Object[10]; 
  7.        } 
  8.       
  9.        public Object get(Object key) { 
  10.              int index = indexFor(hash(key.hashCode()), 10); 
  11.              return table[index]; 
  12.        } 
  13.       
  14.        public void put(Object key, Object value) { 
  15.              int index = indexFor(hash(key.hashCode()), 10); 
  16.              table[index] = value; 
  17.        } 
  18.       
  19.        /** 
  20.        * 通过hash code 和table的length得到对应的数组下标 
  21.        * 
  22.        * @param h 
  23.        * @param length 
  24.        * @return 
  25.        */ 
  26.        static int indexFor(int h, int length) { 
  27.              return h & (length - 1); 
  28.        } 
  29.       
  30.        /** 
  31.        * 通过一定算法计算出新的hash值 
  32.        * 
  33.        * @param h 
  34.        * @return 
  35.        */ 
  36.        static int hash(int h) { 
  37.              h ^= (h >>> 20) ^ (h >>> 12); 
  38.              return h ^ (h >>> 7) ^ (h >>> 4); 
  39.        } 
  40.        
  41.        
  42.        public static void main(String[] args){ 
  43.              SimpleHashMap hashMap = new SimpleHashMap(); 
  44.              hashMap.put("key", "value"); 
  45.              System.out.println(hashMap.get("key")); 
  46.        } 


public class SimpleHashMap {

       private Object[] table;

       public SimpleHashMap() {
             table = new Object[10];
       }

       public Object get(Object key) {
             int index = indexFor(hash(key.hashCode()), 10);
             return table[index];
       }

       public void put(Object key, Object value) {
             int index = indexFor(hash(key.hashCode()), 10);
             table[index] = value;
       }

       /**
       * 通过hash code 和table的length得到对应的数组下标
       *
       * @param h
       * @param length
       * @return
       */
       static int indexFor(int h, int length) {
             return h & (length - 1);
       }

       /**
       * 通过一定算法计算出新的hash值
       *
       * @param h
       * @return
       */
       static int hash(int h) {
             h ^= (h >>> 20) ^ (h >>> 12);
             return h ^ (h >>> 7) ^ (h >>> 4);
       }

      
       public static void main(String[] args){
             SimpleHashMap hashMap = new SimpleHashMap();
             hashMap.put("key", "value");
             System.out.println(hashMap.get("key"));
       }
}

这个简单的例子大概描述了散列实现hashmap的过程

但是还很不成熟,我发现至少存在以下两个问题

1. hashmap的size是固定的

2. 如果不同的key通过hashcode得出的index相同呢,这样的情况是存在的,如何解决?




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论