映射表 map（一）

由于近来学习groovy，看到了其映射表，想知道其实际的结构，而映射表又是计算机技术中一个十分重要的数据结构，所以想写一个系列，仔细探寻一下映射表。
     本篇从数据结构上给以说明，映射表（map）是一种具有key/value（键/值）结构的集合，我的理解这种数据结构其实就是一种功能更强大的数组，key就是数组下标，而value就是下标对应的值，现代语言都对它都有相应的实现。在这里分别对他们[主要包括python，java，groovy，因为我只会这几个语言 :-) ]进行剖析。
      由于hashmap是map最长用的一种实现，所以先说一下hash算法，他是一种计算式的查找方法，基本思想是在k和v的存储位置p之间建立一种函数关系（ p=H(k) ）,然后由k通过函数H计算出p，然后达到直接存储v的目的.而当k的集合很大时，就有相当大的概率使得k1 != k2 时有H(k1) = H(k2)，这种问题就是冲突，所以我们设计H的时候，就是尽力避免冲突。
     那么hash函数的构造方式常见的有：（详细的论述我就不写了，这些都可以从数据结构的书中查到）

• 数字分析法
• 平方取中法
• 分段叠加法
• 除留余数法
• 伪随机数法

     而这些方式都是需要基于key的，而key通常就是hashcode的，也就是用一串数字来代表一个对象，或一个结构，比如java的根类Object中有一个int hashCode();的方法，如果你不去显示的重写它，那么它默认的返回该对象在内存中的地址。
      处理冲突

• 再散列法
• 再哈希法
• 连地址法

建立公共溢出区法
    性能：

• 散列函数是否均匀；
• 处理冲突的方法；
• 散列表的装填因子。

  散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
而α常常是经过大量的实际测算得出的，比如java的hashmap的α为0.75