Hash表的实现——拉链法

一.基础的概念问题

·我们最常用的两种数据结构就是数组和链表，各自的优缺点很明确，对于数组来说，搜索某个下标位置的元素很快，但进行插入和删除操作就很慢，链表在内存中是离散存储的，查找具体某个元素比较慢，但插入删除操作很快。但是有时需要对大量数据进行查找以及插入删除操作，这时就需要用到哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。

·Hash我们百度一下英文意思就是把其弄乱，切碎。那哈希表的实现原理就和英文单词hash很类似。它是将大量数据切碎，每一个数据都看似“杂乱”的存储到一个表的某个位置，事实并不是随意分配，。事实上，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

二.拉链法实现

1.什么是拉链法：也叫做链地址法。拉链发就是把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。

就是下面这种结构

2.拉链法实现的特点

·散列表中存放的不是数据，而是存储数据的链表头结点，也就是说，散列表是一个链表数组。

·当想要存储或者