Java 理论与实践: 哈希

  categories:资料  author:

来源:http://www.ibm.com/developerworks/cn/java/j-jtp08223/

虽然Java语言不直接支持关联数组 — 可以使用任何对象作为一个索引的数组 — 但在根 Object 类中使用 hashCode() 方法明确表示期望广泛使用 HashMap (及其前辈 Hashtable )。理想情况下基于散列的容器提供有效插入和有效检索;直接在对象模式中支持散列可以促进基于散列的容器的开发和使用。

定义对象的相等性

Object 类有两种方法来推断对象的标识: equals()hashCode() 。一般来说,如果您 Override 了其中一种,您必须同时 Override 这两种,因为两者之间有必须维持的至关重要的关系。特殊情况是根据 equals() 方法,如果两个对象是相等的,它们必须有相同的 hashCode() 值(尽管这通常不是真的)。

特定类的 equals() 的语义在Implementer的左侧定义;定义对特定类来说 equals() 意味着什么是其设计工作的一部分。 Object 提供的缺省实施简单引用下面等式:

  public boolean equals(Object obj) 
阅读全文

用户体验测试

  categories:资料  tags:  author:

来源:互联网

1首页可用性设计

[确保用户打开首页的可用性良好,能够明白该如何操作。]

1. 首页元素要清晰的关注用户的关键任务(避免“增加功能倾向”)

2. 如果网站比较大,那么首页应包含搜索输入框

3. 首页要十分清楚的提供产品(内容)分类

4. 信息展示时应当是简单的、自然的、符合逻辑顺序的

5. 在首页展示真实网站内容的优秀示例

6. 首页上的链接简洁明确

7. 在首页提供一个最近的特色项列表,并提供存档内容的链接

8. 首页导航不要过度修饰,确保用户不会把它误认为广告

9. 在首页有清晰的声明价值取向(例如一个标志性的口号或欢迎语)

10. 在首页包含有意义的图案设计,而非无关的剪贴画或绘画作品

11. 导航选项按逻辑性或用户导向方式排序(把次要的公司信息放在底部)

12. 首页标题可以为诸如google等搜索引擎提供良好可见度

13. 所有公司相关信息安排在一个显著区域(例如:“关于我们(About Us)”)

14. 一看到首页,第一次访问的人就知道从何处开始

15. 在首页展示出所有主要的操作选项

16. 首页拥有一个易记的URL

17. 首页需经过专业设计,以给用户良好的第一印象

18. 首页的设计要能激发用户探索站点的兴趣… 阅读全文

MySQL slave状态之Seconds_Behind_Master

  categories:mysql资料  tags:  author:
来源:互联网

在MySQL的主从环境中,我们可以通过在slave上执行show slave status来查看slave的一些状态信息,其中有一个比较重要的参数Seconds_Behind_Master。那么你是否明白它的真正含义以及它是怎么计算的呢?

在之前我一直误以为Seconds_Behind_Master是表示slave比master落后多少,如果这个值为0的表示主从已经处于一致了(在非 同步模式下,现在官方最多也只在5.5中增加了半同步复制)。但是最近我终于认识到之前的错误理解。首先我们需要明白的一 点:Seconds_Behind_Master表示slave上SQL thread与IO thread之间的延迟,我们都知道在MySQL的复制环境中,slave先从master上将binlog拉取到本地(通过IO thread),然后通过SQL thread将binlog重放,而Seconds_Behind_Master表示本地relaylog中未被执行完的那部分的差值。手册上的定义:

In essence, this field measures the time difference in seconds between the slave SQL thread and the slave I/O thread.

所以如果slave拉取到本地的relaylog(实际上就是binlog,只是在slave上习惯称呼relaylog而已)都执行完,此时通过 show slave status看到的会是0,那么Seconds_Behind_Master的值为0是否表示主从已经处于一致了呢?答案几乎是否定的!为什么几乎是否定 的?因为绝大部分的情况下复制都是异步的,异步就意味着master上的binlog不是实时的发送到slave上,所以即使 Seconds_Behind_Master的值为0依然不能肯定主从处于一致,这也是我之前强调非同步复制的原因(现在已经有公司在做同步复制了,比如 网易自己实现了VSR,VirtualSynchronized Replication,由于同步复制性能较差,所以网易再实现同步复制的同时还打了group commit的补丁)。所以如果我们要以这个参数来估计主从延迟多久的话至少得在一个比较好的网络环境中,这样才能保证几乎master上的binlog都已经发送到slave上。… 阅读全文

MySQL server has gone away 问题的解决方法

  categories:mysql资料  tags:  author:

今天在备份自己blog的 数据库时发生错误, 信息如下:

mysqldump: Error 2020: Got packet bigger than ‘max_allowed_packet’ bytes when dumping table `xxx_posts` at row: 716
mysqldump: Couldn’t execute ‘show table status like ‘xxx\_posts\_2\_bak”: MySQL server has gone away (2006)
— Warning: Couldn’t get status information for … 阅读全文

关于用户体验的思考

  categories:资料  author:

来源:互联网

用户体验是一个很大的话题,先从一个故事说起。周末参加了两天的PMP培训,听课期间注意到老师的一个细节,在讲选择题的时候,选项A、C读音正常, 而”B”老师读为Boy,”D”老师读为Dog。刚听到的时候大家莞尔一笑,以为这是个善意的玩笑。但是以后的题目都是这样读音。很快,我想明白了,B和 D的发音类似,容易混淆;Boy和Dog是简单的单词,发音能够明确区分,也没有类似Bog和Doy的读音混淆。这是什么?这就是用户体验。

1. 页面布局

常规上来说,我们把网页布局按照分栏的多少分为一栏式,二栏式和三栏式。

对于一栏式页面布局来说,一般在页面上放置一个具有冲击力的图片或者Flash来给用户留下深刻的印象,但是,这样的页面所能够容纳的信息量非常有限。所 以常用于企业网站,以及一些小网站的首页,用于让用户记住你的站。此外,对于功能性比较单一的页面,也一般用一栏式布局,比如搜索引擎,注册和登录页面等 等。

二栏式布局是最为常见的布局方式,二栏式又分为左宽右窄和左窄右宽式。这两种模式的选择是由于网站的性质所决定的。对于用户来说,他的浏览关注顺序是从左 到右,那么窄的部分一般来说都是导航栏,而宽的部分则是主体内容部分,那么用哪一种方式将取决于你的站是内容占主体还是导航占主体,换句话说,是内容驱动 导航还是导航来驱动内容。

对于三栏式布局来说,最大的好处就在于容纳的信息量比较大,但是重点不突出,降低了用户对网站的可控性,因此一般意义上不推荐。

当然,如果当用户需要比较多样化的时候,也可以让用户自由来设计布局,多常见于个人博客。

2. 页面的通透性

页面的通透性是指尽量使整个页面的模块比例统一,同时通过线条,颜色等视觉元素增加各模块间的区分度,使得用户的视线轨迹可以有规则地通过各个模块,而不会被模块之间不规则的交叉所打断。

此外,根据”F”原则,也应该尽量将重要地,用户所关系地内容放在页面的左上角位置。

3. 页面的配色方案

每个网站都要有自己的主色调,主色调指的就是页面色彩的主要色调,总趋势,其他配色的综合不能超过主色调的50%(白色背景除外)。

在选择颜色的时候,不仅仅要考虑颜色本身所代表的含义,如安全,浪漫等,还有考虑以下几种因素。

目标用户群体。不同的用户群体对于颜色的审美爱好以及理解都不同,其中包括性别,年龄,职业等。

当地文化风俗。如中国把红色作为喜庆的颜色,而欧洲大部分却把红色作为杀戮的象征。

网站的类型。如电子商务站一般用暖色调来刺激用户购买,而SNS站则营造一个轻松的氛围。而垂直类网站一般都与自己的领域特色相关。

品牌形象。我总结一句话就是根据自己的Logo以及企业形象来选择色调。比如IBM就一定会选择蓝色作为主色调。

4. 页头和页尾

页头分为设计型头部和简约型头部。一般的大型网站,由于已经有着一定的网站知名度,所以无需在通过渲染头部来提高网站对用户的吸引力,加深印象。所以一般 采用比较简单的简约型头部,比如新浪,腾讯,都是这样的效果。对于一些小网站来说,采用设计性头部给用户留下深刻印象,创造品牌效应,但是当设计性头部过 于繁杂时,却使得内容的容纳量变小,从而造成一种头重脚轻的感觉。所以这个需要设计师的一种折中。

在页头上最重要的就是Logo,在现代网站的设计中,Logo起到两个作用,一个是标识,一个是让用户回到首页。

页尾一般来说并不重要,用户可到达的机会也少,所以尽量地去简化它,避免它占用内容所占据的位置。

5. 搜索区

现在的网站一般都带有站内搜索的功能,目前有两种设计方式。

一种将搜索淡化,因为搜索只是一种手段,适用于浏览型网站,我并不鼓励你搜索,而是希望你一条一条地看下去。比如说豆瓣。我希望你去看社区的动态,而不是希望你来豆瓣为了找人。

一种是搜索为主,最简单的就是淘宝。一般来说用户来电子商务站都是有着明确的目的,所以搜索是用户找到他想要商品的最主要方式。

另外,对于搜索框来说,如果你鼓励用户使用搜索框,在页面刚刚打开的时候,就可以让光标在搜索框上,这样用户可以直接搜索内容,而省去了一次操作。但是如果并非如此,就不要让光标在文本框上,因为这样用户变没有办法使用键盘来让整个页面下移。

阅读全文

搜索引擎技术简介及一些开源搜索引擎

  categories:搜索资料  tags:,   author:

1.引言

因特网的发展形成了一个巨大的全球化信息空间,方便了信息的收集和获取, 并且信息仍以惊人的速度增长。Web信 息的大容量、异构性、分布性和动态性给信息检索带来了挑战,如何快速获取需要的信息是用户面临的重大问题。搜索引擎技术可用来解决这一问题。搜索引擎以一 定的策略在互联网中搜集、发现信息,对信息进行理解、提取、组织和处理,并为用户提供检索服务,从而起到信息导航的作用。搜索引擎提供的导航服务已成为互 联网上非常重要的网络服务。同时,高性能的Web信息检索技术也是充分利用Web资源发展电子商务、远程教学、数字化图书馆等方面应用的重要基础。目前,搜索引擎技术已成为计算机工业界和学术界争相研究、开发的对象,并逐渐体现其经济价值。

搜索引擎的性能主要取决于:索引数据库的容量、存放内容、以及更新速度,搜索速度,用户界面的友好程度以及是否易用等。搜索引擎是以传统信息检索技术为基础,利用其索引模型、匹配策略等方面的技术成果并针对Web资 源的特点发展起来的信息检索技术,涉及多领域的理论和技术:数字图书馆、数据库、信息检索、信息提取、人工智能、机器学习、自然语言处理、计算机语言学、 统计数据分析、数据挖掘、计算机网络、分布式处理等,具有综合性和挑战性。本文对搜索引擎技术进行了系统的介绍和分析,以工作方式对搜索引擎进行分类,介 绍搜索引擎各组成部分的相关研究和关键技术(搜索器策略、检索策略、搜索结果处理、信息检索Agent、多媒体搜索引擎等),并对未来搜索引擎的主要发展方向进行了展望。

 

2.搜索引擎的分类

按照信息搜集方法、服务提供方式和系统结构的不同,搜索引擎系统可以分为不同的类别,下面介绍按照搜索引擎工作机制对其进行分类。搜索引擎作为用户层和Web信息层之间的中间层,内部结构有所不同。如图1所示,用户可以直接从机器人搜索引擎或者目录式搜索进行检索,或者通过元搜索引擎进行检索,或者通过信息检索Agent进行检索。由此搜索引擎系统可以分为以下类别。

 

1 搜索引擎工作机制分类

1)机器人搜索引擎:由一个机器人(Robot阅读全文

一致性哈希算法与Java实现

  categories:资料  author:
来源:互联网
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节 点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据 迁移,如果是分布式缓存,则其他缓存就失效了。因此,引入了一致性哈希算法:

 

把数据用hash函数(如MD5),映射到一个很大的空间里,如图所示。数据的存储时,先得到一个hash值,对应到这个环中的每个位置,如k1对应到了图中所示的位置,然后沿顺时针找到一个机器节点B,将k1存储到B这个节点中。

如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示:

 

这样,只会影响C节点,对其他的节点A,D的数据不会造成影响。然而,这又会造成一个“雪崩”的情况,即C节点由于承担了B节点的数据,所以C节点的负载会变高,C节点很容易也宕机,这样依次下去,这样造成整个集群都挂了。

为此,引入了“虚拟节点”的概念:即把想象在这个环上有很多“虚拟节点”,数据的存储是沿着环的顺时针方向找一个虚拟节点,每个虚拟节点都会关联到一个真实节点,如下图所使用:


图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点,机器A负载存储A1、A2的数据,机器B负载存储B1、B2的数据,机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成“雪崩”现象。

Java实现:

public class Shard<S> { // S类封装了机器节点的信息 ,如name、password、ip、port等
private TreeMap<Long, S> nodes; // 虚拟节点
private List<S> shards; // 真实机器节点
private final int NODE_NUM = 100; // 每个机器节点关联的虚拟节点个数
public
阅读全文

对等网络(P2P)中主流分布式哈希算法比较分析

  categories:资料  author:

来源:互联网

本文首先从P2P的定义出发,介绍了结构化P2P与非结构化P2P的区别以及结构化P2P的核心技术DHT。而后,本文深入介绍了几种主流的DHT算法与协议并对每种协议进行了讨论。文章的最后展望了DHT在未来的发展趋势。

对 等网络(Peer-to-Peer,简称P2P)是目前非常热门的应用,自1999年以来,P2P的研究一直是国外知名学府(如美国麻省理工学院,加州大 学伯克利分校和莱斯大学等)以及知名企业的研发机构(如微软,诺基亚的研究院)关注的重点。它甚至被美国《财富》杂志称为改变因特网发展的四大新技术之 一,被认为是代表无线宽带互联网未来的关键技术。

作为一项新兴的技术,目前学术界对P2P在技术层面上的定义尚未统一。 Keith W. Ross (Polytechnic University)和Dan Rubenstein(Columbia University)在[9]中提到了对P2P系统的3个基本定义:

相比中央服务器而言有明显的自治性(Autonomy)。

利用网络边缘的资源,如存储/计算能力和信息资源。

网络边缘的资源处在动态的变化中(新的资源加入,已有的资源消失)。

自治性的要求使得P2P系统不再需要特定的中央管理机制,所有节点之间拥有对等的关系。这一方面为系统带来了自组织、容错性好、可扩展性强等优点;另一方面也提出了新的问题:如何在没有集中管理机制的情况下实现系统的自组织和自管理?

定义2,3中分布性和动态性的特点使得上述问题的实现具有更大的难度。在分布式系统中,过多过快的信息交互可能消耗大量的网络资源;而为了实时反映系统的变化,又要求节点及时获得更新信息,这就需要在节点之间进行通信。

为了解决这一对矛盾,已经有许多P2P的框架和协议被提出来并得到了很好的应用。

结构化与非结构化P2P

依照节点信息存储与搜索方式的不同,诸多P2P协议可以分为2大类:结构化(Structured)的与非结构化(Unstructured)的系统。

非结构化P2P系统

在 非结构化的系统中,每个节点存储自身的信息或信息的索引(如指针和IP地址)。当用户需要在P2P系统中获取信息时,他们预先并不知道这些信息(如某个文 件)会在那个节点上存储。因此,在非结构化P2P系统中,信息搜索的算法难免带有一定的盲目性,例如最简单的泛洪式查找(类似于广播)和扩展环查找(从最 近的n个节点开始,层层转发直到找到目标或超出了跳数的上限为止)。

一些典型的应用采用了一些优化的办法。如在Gnutella 中,采用了等级制的组成结构:节点被分成超级节点(Super Node)和普通节点。普通节点必须依附于超级节点,每个超级节点作为一个独立的域管理者,负责处理域内的查询操作。在查找的过程中,查询首先在域内进 行,失败后才会扩展到超级节点之间。

非结构化系统的优点在于实现结构简单:无须中央服务器,节点之间完全平等,网络的层次是单一的,而且节点之间无需维护拓扑信息。

结构化P2P系统

在 结构化P2P系统中,每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时,他们必须知道这些信息(或索引)可能存在于那些节 点中。由于用户预先知道应该搜索哪些节点,避免了非结构化P2P系统中使用的泛洪式查找,因此提高了信息搜索的效率。

但是,结构化P2P也引入了新的问题:

首先,既然信息是分布存储的,那么如何将信息分布存储在重叠网中的节点上?

其次,由于节点动态的加入和离开重叠网,如何将拓扑的变更信息通知其它节点?

DHT

阅读全文

memcached分布测试报告(一致性哈希情况下的散列函数选择)

  categories:资料  author:
一、背景资料memcached本身是集中式的缓存系统,要搞多节点分布,只能通过客户端实现。memcached的分布算法一般有两种选择:
1、 根 据hash(key)的结果,模连接数的余数决定存储到哪个节点,也就是hash(key)% sessions.size(),这个算法简单快速,表现良好。然而这个算法有个缺点,就是在memcached节点增加或者删除的时候,原有的缓存数据 将大规模失效,命中率大受影响,如果节点数多,缓存数据多,重建缓存的代价太高,因此有了第二个算法。
2、Consistent Hashing,一致性哈希算法,他的查找节点过程如下:
首先求出memcached服务器(节点)的哈希值,并将其配置到0~232的圆(continuum)上。然后用同样的方法求出存储数据的键的哈希值,并映射到圆上。然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器,就会保存到第一台memcached服务器上。

一致性哈希算法来源于P2P网络的路由算法,更多的信息可以读这里。

二、测试报告

spymemcached和xmemcached都实现了一致性哈希算法(其实我是照抄的),这里要测试下在使用一致性哈希的情况下,增加节点,看不同散列函数下命中率和数据分布的变化情况,这个测试结果对于spymemcached和xmemcached是一样的,测试场景:
从一篇英文小说(《黄金罗盘》前三章)进行单词统计,并将最后的统计结果存储到memcached,以单词为key,以次数为value。单词个数为 3061,memcached原来节点数为10,运行在局域网内同一台服务器上的不同端口,在存储统计结果后,增加两个memcached节点(也就是从10个节点增加到12个节点),统计此时的缓存命中率并查看数据的分布情况
结果如下表格,命中率一行表示增加节点后的命中率情况(增加前为100%),后续的行表示各个节点存储的单词数,CRC32_HASH表示采用CRC32 散列函数,KETAMA_HASH是基于md5的散列函数也是默认情况下一致性哈希的推荐算法,FNV1_32_HASH就是FNV 32位散列函数,NATIVE_HASH就是java.lang.String.hashCode()方法返回的long取32位的结 果,MYSQL_HASH是xmemcached添加的传说来自于mysql源码中的哈希函数。

CRC32_HASHKETAMA_HASHFNV1_32_HASHNATIVE_HASHMYSQL_HASH
命中率78.5%83.3%78.2%
阅读全文

哈希分布与一致性哈希算法简介

  categories:资料  author:

来源:互联网

前言
在我们的日常web应用开发当中 memcached可以算作是当今的标准开发配置了。相信memcache的基本原理大家也都了解过了,memcache虽然是分布式的应用服务,但分布 的原则是由client端的api来决定的,api根据存储用的key以及已知的服务器列表,根据key的hash计算将指定的key存储到对应的服务器 列表上。

基本的原理以及分布
在这里我们通常使用的方法是根据 key的hash值%服务器数取余数 的方法来决定当前这个key的内容发往哪一个服务器的。这里会涉及到一个hash算法的分布问题,哈希的原理用一句话解释就是两个集合间的映射关系函数, 在我们通常的应用中基本上可以理解为 在集合A(任意字母数字等组合,此处为存储用的key)里的一条记录去查找集合B(如0-2^32)中的对应记录。(题外话:md5的碰撞或者说冲突其实 就是发生在这里,也就是说多个A的记录映射到了同一个B的记录)

实际应用
显然在我们的应用中集合A的记录应该更均匀的分布在集合B的各个位置,这样才能尽量避免我们的数据被分布发送到单一的服务器上,在danga的memcached的原始版本(perl)中使用的是crc32的算法用java的实现写出来:
private static int origCompatHashingAlg( String key ) {
int hash    = 0;
char[] cArr = key.toCharArray();

for ( int i = 0; i < cArr.length;

阅读全文


快乐成长 每天进步一点点