手写字典.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "首先是构造个简单的线性表\n",
    "\"\"\" \n",
    "线性表结构\n",
    "\"\"\"\n",
    "class LinearMap(object):\n",
    "\n",
    "    def __init__(self):\n",
    "         self.items = []\n",
    "     \n",
    "    # 往表中添加元素    \n",
    "    def add(self, k, v):  \n",
    "        self.items.append((k,v))\n",
    "    #     这个是元组\n",
    "\n",
    "    # 线性方式查找元素\n",
    "    def get(self, k): \n",
    "        for key, value in self.items:      \n",
    "            if key == k:      # 键存在，返回值，否则抛出异常\n",
    "                return value\n",
    "        raise KeyError\n",
    "\n",
    "'''\n",
    "我们可以在使用add添加元素时让items列表保持有序，而在使用get时采取二分查找方式，时间复杂度为O(log n)。 \n",
    "然而往列表中插入一个新元素实际上是一个线性操作，所以这种方法并非最好的方法。\n",
    "同时，我们仍然没有达到常数查找时间的要求。\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "将总查询表分割为若干段较小的列表，比如100个子段。\n",
    "通过hash函数求出某个键的哈希值，再通过计算，得到往哪个子段中添加或查找。\n",
    "相对于从头开始搜索列表，时间会极大的缩短。\n",
    "'''\n",
    "class BetterMap(object):\n",
    "      #利用LinearMap对象作为子表，建立更快的查询表\n",
    "    def __init__(self,n=100):\n",
    "        self.maps = []          # 总表格\n",
    "        for i in range(n):      # 根据n的大小建立n个空的子表\n",
    "            self.maps.append(LinearMap())\n",
    "      \n",
    "    def find_map(self,k):       # 通过hash函数计算索引值\n",
    "        index = hash(k) % len(self.maps)\n",
    "        # 这里是取余，后面的长度是定值，那么每一个k的index是不同的\n",
    "        return self.maps[index] # 返回索引子表的引用     \n",
    " \n",
    "     # 寻找合适的子表（linearMap对象）,进行添加和查找\n",
    "    def add(self, k, v):\n",
    "        m = self.find_map(k)        \n",
    "        m.add(k,v)\n",
    "     \n",
    "    def get(self, k):\n",
    "        m = self.find_map(k)\n",
    "        return m.get(k)\n",
    "    # 查找的时候只需要计算一下前面的取余就行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashMap(object):\n",
    "    def __init__(self):\n",
    "        # 初始化总表为，容量为2的表格（含两个子表）\n",
    "        self.maps = BetterMap(2)\n",
    "        self.num = 0        # 表中数据个数\n",
    "      \n",
    "    def get(self,k):        \n",
    "        return self.maps.get(k)\n",
    "      \n",
    "    def add(self, k, v):\n",
    "        # 若当前元素数量达到临界值（子表总数）时，进行重排操作\n",
    "        # 对总表进行扩张，增加子表的个数为当前元素个数的两倍！\n",
    "        if self.num == len(self.maps.maps): \n",
    "            self.resize()\n",
    "         \n",
    "        # 往重排过后的 self.map 添加新的元素\n",
    "        self.maps.add(k, v)\n",
    "        self.num += 1\n",
    "         \n",
    "    def resize(self):\n",
    "        #重排操作，添加新表, 注意重排需要线性的时间\n",
    "        # 绝大部分时间是常数，偶尔线性\n",
    "        # 先建立一个新的表,子表数 = 2 * 元素个数\n",
    "        new_maps = BetterMap(self.num * 2)\n",
    "         \n",
    "        for m in self.maps.maps:  # 检索每个旧的子表\n",
    "            for k,v in m.items:   # 将子表的元素复制到新子表\n",
    "                new_maps.add(k, v)\n",
    "         \n",
    "        self.maps = new_maps      # 令当前的表为新表"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}