基础概念

散列表

• 散列表是一种将键（Key）映射为值（Value）从而快速查找的数据结构
• 散列表包含一个底层数组和一个散列函数（hash function）,插入一个对象及对应的键时，散列函数会将键映射为数组的一个索引，这个对象就会被存在数组的索引位置上
  • 但是，会发生“碰撞”，不同的键映射到数组的同一个索引
  • 将对象的存储在索引为 hash(Key) % array_length 的数组元素指向的链表中，要通过键来查找对象，先从散列表找到对应的链表，再用键匹配链表的对象，找到相应的对象

动态数组

• arrayList:数据访问的时间为O(1)
• 数组存满时将其扩大2倍

stringBuffer

• 避免频繁创建string对象
• 线程安全

链表

• 注意链表插入，删除时的指针更新操作
• 单链表和双链表
• 链表逻辑上连续，但是物理空间不一定连续；数组是逻辑和空间都连续的数据接口
• 链表插入，删除速度快；数组查询速度快

操作	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

链表技巧

栈与队列

• 栈采用后进先出（LIFO）,可以使用链表构建一个栈，新增元素放在表头，只对外界开放表头元素
• 队列采用先进先出（FIFO）, 可以使用链表构建队列，新增元素放在表尾，从表头遍历元素