加载中…
个人资料
Yode
Yode
  • 博客等级:
  • 博客积分:0
  • 博客访问:592,745
  • 关注人气:250
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

合适的数据存储结构

(2010-06-12 16:53:02)
标签:

it

分类: 垂直搜索引擎
    最近涉及到要将大批量的数据存储,读取以及判断是否存在。 开始简单的用hashtable来实现,而且直接存的string,在load的时候很占内存,将string先hash一下会好很多。另外hashtable是线程安全的,hashmap是不
安全的。首先来看一下它们的区别。
  • Hashtable是Dictionary的子类,HashMap是Map接口的一个实现类;
  • Hashtable中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。即是说,在多线程应用程序中,不用专门的操作就安全地 可以使用Hashtable了;而对于HashMap,则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得 到解决:

          Map Collections.synchronizedMap(Map m)
    这个方法返回一个同步的Map,这个Map封装了底层的HashMap的所有方法,使得底层的HashMap即使是在多线程的环境中也是安全的。

  • 在HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,即 可以表示HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在 某个键,而应该用containsKey()方法来判断。
  • 其底层的实现机制不同,hashmap的访问速度要快于hashtable,因为它不需要进行同步检验,建议在非多线程环境中使用hashmap代替hashtable .

 
     HashTable的应用非常广泛,HashMap是新框架中用来代替HashTable的类,也就是说建议使用HashMap,不要使用HashTable。可能你觉得HashTable很好用,为什么不用呢?这里简单分析他们的区别。

  •  HashTable的方法是同步的,HashMap未经同步,所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。
  • HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。
  • HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样。
  • HashTable使用Enumeration,HashMap使用Iterator。
  • HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。
  • 哈希值的使用不同,HashTable直接使用对象的hashCode,代码是这样的:

        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
     而HashMap重新计算hash值,而且用与代替求模:
     int hash = hash(k);
     int i = indexFor(hash, table.length);

     static int hash(Object x) {
      int h = x.hashCode();

      h += ~(h < < 9);
      h ^= (h >>> 14);
      h += (h < < 4);
      h ^= (h >>> 10);
      return h;
     }
    static int indexFor(int h, int length) {
     return h & (length-1);
    }
     当一个url被处理后,会从中抽取很多新的链接,这些新的链接需要被Frontier的一addElement方法加入到队列中继续处理。但是,在将这些新链接加入到队列之前,要首先做一个检查,即isAlreadyIncluded在这个HashMap中,查看当前要加入到队列中的链接是否在先前已经被处理过了。 当使用HashMap来存储那些已经被处理过的链接时,HashMap中的key为url,而value则为一个对url封装后的对象。很显然的,这里有几个问题。 
  •  对这个HashMap的读取是多线程的,因为每个线程都需要访问这个HashMap,以决定当前要加入链接是否已经存在过了。
  •  对这个HashMap的写入是多线程的,每个线程在处理完毕后,都会访问这个HashMap,以写入最新处理的链接。
  • 这个HashMap的容量可能很大,可以试想,一次在广域网范围上的网页抓取,可能会涉及到上十亿个URL地址,这种地址包括网页、图片、文件、多媒体对象等,所以,不可能将这么大一张表完全的置放于内存中。 综合考虑以上3点,仅用一个HashMap来保存所有的链接,显然已经不能满足“大数据量,多并发”这样的要求。因此,需要寻找一个替代的工具来解决问题,于是就引入了 Bekerley DB.
    简单的说,Berkeley DB就是一个HashTable,它能够按“key/value”方式来保存数据。它是由Sleepycat公司开发的一套开放源代码的嵌入式数据库,它为应用程序提供可伸缩的、高性能的、有事务保护功能的数据管理服务。那么,为什么不使用一个传统的关系型数据库呢?这是因为当使用BerkeleyDB时,数据库和应用程序在相同的地址空间中运行,所以数据库操作不需要进程间的通讯。然而,当使用传统关系型数据库时,就需要在一台机器的不同进程间或在网络中不同机器间进行进程通讯,这样所花费的开销,要远远大于函数调用的开销。 另外,Berkeley DB中的所有操作都使用一组API接口。因此,不需要对某种查询语言(比如SQL)进行解析,也不用生成执行计划,这就大大提高了运行效率。

     当然,做为一个数据库,最重要的功能就是事务的支持,Berkeley DB中的事务子系统就是用来为其提供事务支持的。它允许把一组对数据库的修改看作一个原子单位, 这组操作要么全做,要么全不做。在默认的情况下,系统将提供严格的ACID事务属性,但是应用程序可以选择不使用系统所作的隔离保证。该子系统使用两段锁 技术和先写日志策略来保证数据的正确性和一致性。这种事务的支持就要比简单的HashTable中的Synchronize要更加强大。


 


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:linux终端切换
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇linux终端切换
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有