多敲！！！多敲！！！多敲！！！（多用手写代码，多使用记事本去写）好记心不如烂笔头
 
基本上每一个初学者都会遇到这样的问题，包括我之前也是一样，导致的原因就是自己不喜欢动手，就算自己有了思路，却不知道从何下手；因为在你的脑海中一直对这些题目都是存在于数学上面的操作，真的要使用代码去实现的时候你脑子就会一篇空白
 
一个代码写多了的人，不管你的需求再难，他也能写出一个基本的框架出来，也不至于无从下手，因为代码写多了的人都会总结出一套规律，开发都是这一个套路
 
就跟你建房子一样，基本的框架搭建完毕之后，只需要慢慢砌砖就行了
 
所以，学习Java最注重的就是实操，大家都知道去一个公司之后都是动手敲代码，而不是在旁边指挥，因为公司不会给你这么大的权力，你也达不到这样的级别，所以公司要的是能够写代码的人，你的理论在这里没有太大的作用
 
 
 
站在岸上学不会游泳的道理大家都应该知道
 
Java学习路线
 
第一阶段：
 
学习java首先是得安装配置jdk
 
下面开始我们愉快且掉头发的java之旅
 
1、入门的基本礼仪：HelloWord
 
2、Java基础语法
 
3、Java条件结构
 
4、Java循环结构
 
第二阶段：
 
数组：数组作为java里面的第一个可以存储数据的容器，也是后面集合的基础
 
第三阶段：
 
面向对象：万物皆可对象，这也是java的核心思想，编程的时候也要面向对象编程，符合Java的编程规范
 
JVM：了解Java中的变量、常量、引用在JVM中国的存储区域
 
第四阶段：
 
Java常用类库：String字符串的应用、Math和Date、集合框架、异常处理、反射
 
第五阶段：
 
IO流：字节流、字符流、其他流、文件读写及编辑、文件上传下载
 
第六阶段：
 
多线程与网络编程
 
第七阶段：数据库
 
Mysql数据库：
 
数据库基础
 
数据库的安装
 
使用语句建表
 
使用语句进行增、删、改、查
 
多表查询
 
子查询
 
复合查询
 
分页查询
 
分组查询
 
数据字典
 
访问控制
 
存储过程
 
可视化工具的使用
 
JDBC：
 
JDBC基础
 
ORM
 
JDBC高级
 
如果你正在入门学习Java或者即将学习，可以申请加入我的Java学习交流QQ裙：639714511，有什么问题都可以随手来交流分享，群文件我上传了我做Java这几年整理的一些学习手册，面试题，开发工具，PDF文档书籍教程，需要的话你们都可以自行来获取下载。
 
群链接：点击链接加入群聊【Java技术讨论群-9群】：
 
 
 
 
HTML：
 
HTML基础
 
HTML常用标签
 
HTML表格
 
HTML表单
 
HTML多媒体
 
网页整体结构
 
CSS:
 
CSS选择的样式
 
CSS文本样式
 
CSS背景和列表
 
CSS盒子模型
 
Float浮动
 
CSS定位
 
CSS网页布局
 
CSS网页布局基础
 
JS:
 
JavaScript基础语法
 
JavaScript流程控制语句
 
JavaScript函数
 
JavaScript内置对象
 
JavaScriptDOM基础
 
JavaScriptDOM事件
 
JavaScript实现轮播效果
 
JQuery：
 
Ajax基础
 
JQuery选择器
 
JQuery属性操作
 
JQuery常用函数
 
JQuery事件处理
 
JQuery异步请求
 
第九阶段：Javaweb
 
JAVAWEB：
 
JAVAWEB核心基础
 
JAVAWEB中jsp及java脚本指令
 
Jsp中隐式对象
 
Servlet核心处理器
 
Jsp与servlet实现登录
 
JAVAWEB中的session
 
JAVAWEB的会话跟踪
 
Jsp动作应用
 
Jsp的EL表达式
 
JSTL标签使用
 
JSTL循环迭代
 
JSTL EL综合练习
 
AOP编程
 
Filter过滤器应用实例
 
JAVAWEB文件上传下载
 
MVC模型
 


  
 
第十阶段：高级框架
 
springFramework构建javaweb应用：
 
springFramework框架概述
 
使用注解把类托管给spring
 
Lod4j
 
Spring整合JDBC
 
JDBC Template实现数据操作
 
SpringMVC应用基础核心
 
视图解析器和RequestMapping注解
 
控制请求方法的参数设置
 
视图转发、重定向
 
Mybatis框架的应用：
 
Mybatis黑心基础概述
 
Mybatis全局配置
 
Mybatis基本查询映射
 
Mybatis更新映射和缓存
 
Mybatis查询结果的封装和高级映射
 
Mybatis动态SQL
 
SPring整合Mybatis
 
第十一阶段：扩展内容
 
Junit
 
设计模式
 
GIT/SVN代码管理器
 
Redis
 
Maven
 
Springboot
 
Springcloud
 
Linux
 
Shiro
 
springSecurity
 
Elasticsearch
 
Lucene
 
Vue
 
Oracle
 
Spring Data JPA
 
 
 
抄代码虽然是程序员的日常，但是初学者非常不建议去抄代码，抄的代码只会让你越抄越乱，从而使自己的思维就依赖在了百度上，自己一点思维都没有，那有如何去提升自己呢
 
代码一定要有自己的思路，然后再把自己的思路转为代码实现，这才是学习Java的正确方式
 


  
 
 

 
初学者要看懂代码首先从要需求分析了解，然后是系统分析，最后是块的理解。看懂代码其实不难，大抵不过是选择，分支，循环。
 

 
初学者怎样看懂代码
 
1、初学者要看懂代码首先从要需求分析了解，然后是系统分析，最后是块的理解。
 
2、看懂代码其实不难，大抵不过是选择，分支，循环。
 
3、语法如果看不懂，那就需要补补基础，先弄清楚这段代码要做什么，有说明最好，可以帮你理解，没有说明就自己试着过一下代码流程。
 
想要看懂代码，建议是首先学习C语言等基础语言有一个基本了解，想要看懂代码及学好编程应该做好如下几步：
 
1、选定方向
 
编程的世界是多元纷繁的，大的方向就分前端开发、后端开发、移动开发、云计算、数据处理、智能硬件、物联网、虚拟现实等等，光编程语言都几十种。如果没有做过功课，贸然进入只会分分钟懵逼。所以最好是根据自己的兴趣爱好再结合市场前景，先选定一个方向，再选择一门语言，然后头也不回的深深扎进去。
 
2、优化学习方式
 
做好笔记，记录经验，我们大多数人并没有过目不忘的神技，很多时候我们学了也不一定马上掌握，需要过后花时间慢慢领悟，而且还有忘掉的风险，所以对于重要的知识点都要做好笔记。
 
3、多看官方文档，外文资料
 
互联网是一个更新迭代很快的行业，所有编程语言都会不断的更新新功能和修复旧Bug，网上查的资料很有可能是旧的解决方案，现在已经不适用了。所以最好最快的方法就是查看官方文档。
 
代码的种类有哪些
 
1、机器语言
 
是最低级的语言，是由二进制码组成，是最早期的一种程序语言。
 
2、技术回功能代码答
 
这种代码与业务，与要实现的系统完全没有依赖，各个编程语言标准库，框架都属于此类，这类代码尽量按不同技术进行独立，保证代码的正确性。如实在需要大量类型组合出需要的功能，如Web框架，设计的功能很多，则应该使用接口，尽量隔离不同的功能，技术。
 
3、业务中功能的实现代码
 
这种代码需要实现业务逻辑，一般会存取业务数据，转换数据结构，检查数据是否符合要求，调用功能类库等，这类代码关联的东西很多，需要做到尽量简单，等分离出去的尽量分离出去，简单一来不容易出问题，二来只需要少量测试即可保证这部分代码的正确性。

引言
 
单链表在数据结构中是很重要的一种线性结构，它是单向的，有着非常广泛的应用领域；虽然现在很多语言中都有封装好的链表类型可以直接使用，但是自己能写一个链表并实现基本操作是至关重要的；
 
接下来我将用代码展示单链表的创建和一些基本操作；
 注：以下代码仅供参考，并不一定是最优代码，只是想让各位了解单链表如何进行的一些基本操作；
 
单链表的结构
 
单链表就是由一个一个节点组成，这个节点由一个数据域和指针域组成；
 如图：
 
 所以，我们需要先创建节点结构，然后才能依次组成单链表；
 注：以下链表的数据域的数据类型都是int类型，实际情况可以修改为任意数据类型；
 
这里使用结构体来创建，代码如下：
 
// 单链表节点结构
typedef struct Node {
	int data; // 数据域
	struct Node* next; // 指针域
}NODE;
 
可以看到，指针域指向的其实就是该节点本身的数据类型，所以这一点一定要注意！
 
单链表的初始化和创建
 
有了基本组成单元，那么就要创建链表了，这里我分为两个函数来实现：
 
void initList(NODE*& head); // 初始化链表
void creatList(NODE*& head); // 创建一个链表
 
初始化链表很简单，直接看代码：
 
// 初始化链表
void initList(NODE*& head) {
	try {
		head = new NODE;
	}
	catch (bad_alloc& e) {
		cout << "内存分配失败！！" << endl;
		cout << e.what() << endl; // 输出异常信息
	} // 捕获异常
	head->data = 0;
	head->next = NULL;
	return;
}
 
这里还有一点值得一提：
 当链表内存分配失败时，我是用的是try…catch捕获的异常，这个使用于现在的大部分新版的编译器，因为新版编译器在内存分配失败的情况下将不再会返回NULL；老版的编译器入VC++6.0等就会返回NULL，所以一定要注意对内存分配失败的处理；
 
接下来就是创建一个单链表了，这里使用的是尾插法；
 为什么使用尾插法呢？因为头插法输出的链表和输入的顺序是相反的，所以最好使用尾插法来创建链表；
 
这里创建的链表也需要注意：
 该链表创建时会有一个没有什么实际意义的头节点，它的数据域存放的是链表的长度，当然创建头节点的目的也是为了方便对链表的操作；
 
代码如下：
 
void creatList(NODE*& head) {
	// 1，确定创建链表长度
	int len;
	cout << "请输入创建链表长度：" << endl;
	cin >> len;
	// 链表长度不应该为0和负数
	if (len <= 0) {
		cout << "创建链表长度不能是0或负数" << endl;
		return;
	}
	head->data = len; // 头节点数据域存放链表长度

	// 2，创建一个尾节点
	NODE* tail = head; // 定义一个节点为尾节点，指向头节点，它将代替头节点移动
	tail->next = NULL;

	// 3，循环创建新的节点
	for (int i = 0; i < len; ++i) {
		cout << "请输入第" << i + 1 << "个数据" << endl;
		int val;
		cin >> val;
		NODE* newNode = NULL;// 创建一个新节点作为临时节点
		try {
			newNode = new NODE; 
		}
		catch (bad_alloc& e) {
			cout << "内存分配失败！！" << endl;
			cout << e.what() << endl;
		} // 捕获异常
		newNode->data = val; // 新节点数据域赋值
		tail->next = newNode; // 将新节点挂在尾节点后面
		newNode->next = NULL; // 新节点指针域为空
		tail = newNode; // 尾节点为新的节点
	}
	return;
}
 
这一步的操作一定要学会，因为只有创建出来链表后你才能对链表进行其他操作；
 
遍历输出链表和链表长度
 
下面的操作是遍历链表并输出和返回链表的长度；
 
为什么把这两个函数放一起？因为它们的操作可以说是一模一样，只是有很小的改动；
 
当然对链表遍历也是非常简单，所以不需要有太大的心理负担；
 

 遍历输出链表代码如下：
 
void traverseList(NODE* head) {
	NODE* p = head->next; // 临时节点p指向头节点的下一个节点
	while (p) {
		cout << p->data << " ";
		p = p->next; // p移向下一个节点
	}
	cout << endl;
	return;
}
 
虽然简单，但是还是需要注意一点：
 临时节点不要忘记，因为头节点是没有什么实际意义的节点，所以输出头节点并没有什么意义；
 
获取链表长度代码如下：
 
int listLength(NODE* head) {
	NODE* p = head->next; // 临时节点p指向头节点的下一个节点
	int len = 0; // 链表长度
	while (p) {
		++len; // 长度加一
		p = p->next; // p移向下一个节点
	}
	return len;
}
 
是不是很简单，只是只需要修改关键的一句代码即可求得链表长度；
 
排序操作
 
有时我们可能会遇到一些情况需要对链表进行排序，链表是线性存储结构，那么该如何排序呢？
 其实也很简单，只需要将数据域的内容进行交换排序即可，也就是只对数据域进行操作，并不改变链表结构；
 
这里是顺序排序；
 代码如下：
 
void sortList(NODE*& head) {
	int t;
	NODE* p;
	NODE* q;
	for (p = head->next; p != NULL; p = p->next) {
		for (q = p->next; q != NULL; q = q->next) {
			// 交换数据域的内容
			if (p->data > q->data) {
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
}
 
这个排序算法并不是最优的，但是非常好理解，所以先学会一种方法再去突破吧！
 
插入操作和删除操作
 
单链表和数组都是线性存储结构，数组的优点是：可以实现快速查询；链表的的优点是：可以快速的实现插入和删除操作；
 所以，插入和删除操作在单链表中是非常非常非常重要的！！
 
对于链表的插入和删除操作，只需要记住一点：插入/删除哪个位置，一定要找到该位置的前一个位置；
 
还是画个图吧：
 
 我来描述一下这张图：
 
想要在data3的位置插入新节点节点s，首先需要找到data3的前一个位置：data2的位置，也就是p指针指向的位置；
接下来就是插入操作了
第一步1：先把新节点s挂到data3上；（即让s节点指向data3节点）
第二步2：断开p节点和data3节点的联系；
第三步3：让p节点指向s节点；（即p节点指针域存放s节点地址）
 
下面就来看一下代码：
 
void insertListByPostion(NODE*& head, int data, int pos) {
	int i = 1;
	NODE* p = head;
	while (p && i < pos) {
		++i;
		p = p->next;
	}
	if (!p || i > pos) {
		cout << "插入位置不存在！！" << endl;
		return;
	}
	NODE* newNode = NULL;
	try {
		newNode = new NODE;
	}
	catch (bad_alloc& e) {
		cout << "内存分配失败！！" << endl;
		cout << e.what() << endl;
	} // 捕获异常
	newNode->data = data;
	newNode->next = p->next;
	p->next = newNode;
	head->data++;
	cout << "插入成功！！" << endl;
}
 
需要注意：插入节点位置必须存在，即首部尾部和中间，所以前面需要先判断插入位置是否存在；
 

 删除操作更简单，如图：
 
 同样描述一下该图：
 
想要删除q节点，所以先找到q节点前一个位置：p节点；
接下来是删除操作：
第一步：让p节点指向r节点
第二步：释放q节点内存空间
 
是不是很简单；
 
来看一下代码如何实现：
 
void deleteListByPostion(NODE*& head, int pos) {
	int i = 1;
	NODE* p = head;
	while (p->next && i < pos) {
		p = p->next;
		++i;
	}
	if (!p->next || i > pos) {
		cout << "删除位置不存在！！" << endl;
		return;
	}
	NODE* q = p->next;
	p->next = q->next;
	cout << "删除成功！！删除元素为：" << q->data << endl;
	delete q;
	head->data--;
}
 
同样需要注意：删除节点位置必须存在，所以需要先判断插入位置是否存在，因为删除只能删除节点只能删除存在的节点，所以判断条件和插入节点有些不同，不理解可以画个图细细品味；
 
按顺序合并两个有序链表
 
这个操作其实已经不算是单链表的基本操作了，它是将两个顺序的链表合并为一个顺序的链表，并且使用O(1)的空间复杂度，既不能使用额外空间，但是考研时经常会出现，所以就来实现一下；
 其实力扣上有原题，可以看看我的这篇文章：21. 合并两个有序链表(C语言)，这里就不再写解析了；
 
代码如下：
 
void mergeTwoLists(NODE*& l1, NODE*& l2, NODE*& list) {
	list->data = l1->data + l2->data; // 头节点数据域为两个链表个数之和
	NODE* p = list;
	NODE* list1 = l1->next; // list1为l1头节点下一个节点
	NODE* list2 = l2->next; // list2为l2头节点下一个节点
	// 要对没有头节点的链表进行操作，一定不能带上头节点进行比较
	while (list1 && list2) {
		if (list1->data < list2->data) {
			p->next = list1;
			list1 = list1->next;
		}
		else {
			p->next = list2;
			list2 = list2->next;
		}
		p = p->next;
	}
	p->next = list1 ? list1 : list2;
	return;
}
 
其实这里还是需要注意一点：
 力扣上的测试链表是没有头指针的，所以我们的链表不能直接去使用力扣上的代码，需要进行一些小改动，但是基本的算法思想还是一样的；
 
逆序链表
 
这个操作是将链表逆置，且同样不能使用额外内存空间；这个力扣上也有原题，解析可以看看我的这篇文章：剑指 Offer 24. 反转链表(C语言)
 
这个操作其实非常简单，就是一个双指针操作；
 
代码如下：
 
void reverseList(NODE*& head, NODE*& list) {
	// 双指针
	list = head; // 先把头节点连接到新的链表上
	NODE* fast = head->next;
	NODE* slow = NULL;
	while (fast) {
		NODE* node = fast->next;
		fast->next = slow;
		slow = fast;
		fast = node;
	}
	list->next = slow;
}
 
同样需要注意：
 力扣上的测试链表是没有头指针的，所以我们的链表不能直接去使用力扣上的代码，需要进行一些小改动，但是基本的算法思想还是一样的；
 
总结
 
链表的操作其实是非常多的，这里只是为你开一个头，不管你是刚学习数据结构的小白，还是有经验的老手，都希望这篇文章可以给你带来一些启发；
 数据结构的学习并不一定会让你瞬间感觉到编程能力的提升，这也是很多人学完数据结构感觉没什么用的原因；但是正是数据结构描述了我们生活抽象的事物，让它们变成了代码展示出来，数据结构在你的编程路上是要一直学习和理解的，只有对底层有更深入的了解，你的编程之路才能走的更顺更远！！！
 希望我们一起进步！！
 
欢迎大家的点评！

输入一个错误的英文单词，它就会提示“拼写错误”。这个单词拼写检查功能，虽然很小但却非常实用。是如何实现的呢？
 
1 什么是散列？
 
散列表，Hash Table，用数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。
 
假如有89名候选人参加大选。为了方便记录投票，每个候选人胸前会贴上自己的参赛号码。这89名选手的编号依次是1到89。
 通过编号快速找到对应的选手信息。你怎么做？
 
可以把这89人的编号跟数组下标对应，查询编号x的人时，只需将下标为x的数组元素取出，时间复杂度就是O(1)。看来按编号查对应人信息，效率很高。
 
这就是散列，编号是自然数，并且与数组的下标一一映射，所以利用数组支持根据下标随机访问时间复杂度是O(1)，即可实现快速查找编号对应的人信息。
 
假设编号不能设置这么简单，要加上州名、职位等更详细信息，所以编号规则稍微修改，用6位数字表示。比如051167，其中，前两位05表示州，中间两位11表示职位，最后两位还是原来的编号1到89。
 
 
 
此时如何存储选手信息，才支持通过编号来快速查找人信息？
 
 
可以截取编号的后两位作为数组下标，来存取候选人信息数据。当通过编号查询人信息时，同样取编号后两位，作为数组下标读取数组数据。
 
这就是散列。候选人编号叫作键（key）或关键字，以标识一个候选人。把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash值”“哈希值”）。
 
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
 
1.1 装载因子（load factor）
 
表示空位的多少：
 
散列表的装载因子=填入表中的元素个数/散列表的长度
 
装载因子越大，说明空闲位置越少，哈希冲突概率越大，插入过程要多次寻址或拉长链，查找也会因此变得很慢。
太小，会导致内存浪费严重。
 
1.2 哈希表碰撞攻击
 
有些攻击者会构造数据，使得所有数据经过hash函数后同槽。若使用的链表法，这时哈希表就会退化为链表，查询时间复杂度从O(1)急剧退化为O(n)。
 
若哈希表有10w数据，退化后的hash表查询效率就下降10万倍。若之前运行100次查询需0.1s，则现在需1w s。这就可能消耗大量CPU或线程资源，导致系统无法响应其他请求，即拒绝服务攻击（DoS）。
 
2 hash函数
 
即hash(key)，其中key表示元素的K值，hash(key)的值表示经过散列函数计算得到的hash值。
 
若编号就是数组下标，所以hash(key)就等于key。改造后的例子，写成hash函数稍微有点复杂。我用伪代码将它写成函数就是下面这样：
 
int hash(String key) {
  // 获取后两位字符
  string lastTwoChars = key.substr(length-2, length);
  // 将后两位字符转换为整数
  int hashValue = convert lastTwoChas to int-type;
  return hashValue;
}
 
但现实都是复杂的，若候选人编号是随机生成的N位数或a到z之间的字符串，散列函数该如何实现？
 
2.1 要求
 
散列函数计算得到的散列值是个非负整数
 因为数组下标从0开始
若key1 = key2，则hash(key1) == hash(key2)
若key1 ≠ key2，则hash(key1) ≠ hash(key2)
 此要求看起来合理，但实际上几乎找不到一个不同key对应散列值都不同的散列函数，即使如MD5、SHA、CRC。而且数组存储空间也是有限的，散列冲突概率就更大了。
不能太复杂
 过度复杂会消耗大量计算时间，影响hash表性能
hash函数生成的值要尽可能随机并且均匀分布
 避免或最小化哈希冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会数据倾斜
 
2.2 案例
 
处理手机号码，因为手机号码前几位重复的可能性很大，但后面几位就比较随机，可以取手机号后四位作为散列值。这种设计方法称为“数据分析法”。
 
单词拼写检查功能的hash函数可考虑：
 
将单词中每个字母的ASCll码值“进位”相加
再跟哈希表的size求余、取模，作为散列值
 
比如，英文单词java，我们转化出来的散列值就是下面这样：
 
hash("java")=(("j" - "a") * 26*26*26 + ("a" - "a")*26*26 + ("v" - "a")*26+ ("a"-"a")) / 78978
 
还有很多设计方法，比如直接寻址法、平方取中法、折叠法、随机数法等。hash函数设计的好坏，决定了哈希表冲突的概率大小，也直接决定了哈希表的性能。
 
无论设计的多么优秀，还是得考虑如何解决散列冲突问题。
 
3 散列冲突
 
3.1 开放寻址法
 
若出现hash冲突，就重新探测一个空闲位置，将其插入。
 最简单的就是
 
3.1.1 线性探测（Linear Probing）
 
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。如ThreadLocalMap。
 
案例
 
黄块
 空闲位置
橙块
 已存储数据
 
 
散列表的大小10，在元素x插入散列表之前，已有6个元素在散列表。
 x经过Hash算法后，被hash到下标7处，但该位置已有数据，所以hash冲突。
 顺序再往后一个个找，看有无空闲位置，遍历到尾部都没有空闲位置，就再从表头开始找，直到找到空闲位置2插入。
 
查找元素
 
类似插入过程。通过hash函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素：
 
若相等
 则为目标元素
否则
 继续顺序往后查找
 
若遍历到数组中的空闲位置，还没找到，说明目标元素不在散列表。
 
 
线性探测法的散列表，删除操作不能单纯地把要删除的元素置null。这是为什么呢？
 查找时，一旦通过线性探测方法，找到一个空闲位置，即可认定散列表不存在该数据。
 但若该空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。
 
可以将删除的元素，特殊标记为deleted。当线性探测查找时，遇到deleted空间，并不是停下来，而是继续往下探测。
 
 
缺陷
 
线性探测法其实存在很大问题。当散列表中数据越多，hash冲突可能性越大，空闲位越少，线性探测时间越久。
 极端情况下，可能需探测整个散列表，所以最坏时间复杂度O(n)。
 
删除和查找时，也可能线性探测整张散列表，才能找到要查找或删除的数据。
 
二次探测（Quadratic probing）
 
双重散列（Double hashing）
 
类似线性探测，线性探测每次探测的步长是1，那它探测的下标序列就是
 
hash(key)+0
hash(key)+1
hash(key)+2
。。。
 
二次探测探测的步长就变成了原来的“二次方”，即探测的下标序列是：
 
hash(key)+0
hash(key)+12
hash(key)+22
……
 
双重散列就是不仅要使用一个散列函数，而使用一组散列函数：
 先用第一个散列函数，如果计算得到的存储位置已被占用，再用第二个散列函数，直到找到空闲位。
 
不管哪种探测方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。
 
优点
 
不像链表法，需要拉很多链表。数据都存在数组中，可有效地利用CPU缓存加快查询速度
序列化也更简单。链表法包含指针，序列化比较麻烦。
 
缺点
 
删除数据时，需特殊标记已删除的数据
所有的数据都存储在一个数组中，冲突的代价更高
 
所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
 
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是Java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
 
3.2 链表法
 
相比开放寻址法简单。
 散列表中，每个“桶（bucket）”或“槽（slot）”对应一条链表：散列值相同的元素放到相同槽位对应的链表。
 
 
插入时，只需通过hash函数计算对应槽位，将其插入到对应链表，时间复杂度O(1)。
 
查找、删除
 
同样通过hash函数计算出对应槽，然后遍历链表查找或删除。
 时间复杂度都和链表长度k成正比，即O(k)，所以查询的效率并非简单地O(1)，若hash函数设计得不好或loadFactor过高，都可能导致散列冲突发生的概率升高，查询效率下降。
 
对于散列均匀的hash函数，理论上：
 
k=n/m
 
其中n表示散列中数据的个数，m表示散列表中“槽”的个数。
 
优点
 
对内存的利用率比开放寻址法要高
 因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。这也是链表优于数组的地方。
对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于1的情况。接近1时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。
 
缺点
 
链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这方面对于执行效率也有一定的影响。
 
存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4个字节或者8个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。
 
对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。
 
 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
 
4 扩容
 
没有频繁插入和删除的静态数据集合，即使实习生也能轻松根据数据特点，设计出优秀的hash函数
而动态hash表，数据频繁变动，无法预估数据个数，所以无法预申请一个足够的hash表。随数据越多，装载因子就会慢慢变大。当装载因子大到一定程度后，哈希冲突就会令程序窒息，此时资深的程序员们该咋办呢？
 
针对hash表，当 loadFactor 过大，可进行动态扩容，新申请更大的hash表，将数据迁移至新hash表。
 假设每次扩容，申请一个原来hash表两倍size的。若原hash表装载因子0.8，则扩容后的新hash表装载因子就降为原来的一半0.4了。
 
但hash表的扩容，数据搬移操作要复杂很多。因为哈希表的大小变了，数据的存储位置也变了，需通过hash函数重新计算每个数据的存储位置。
 
原来hash表的21存储在0位，迁移新hash表后存储在7位。
 
 
 
 
动态扩容的散列表，插入操作的时间复杂度是多少呢？
 
 
插入一个数据：
 
最好无需扩容，时间复杂度O(1)
最坏情况，hash表loadFactor过高，开启扩容新申请内存空间，重新计算哈希位置并迁移数据，时间复杂度O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是O(1)。
 
动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。
 如果对空间消耗非常敏感，可以在装载因子小于某个值之后，启动动态缩容。
 如果更在意执行效率，能够容忍多消耗一点内存空间，就不用费劲缩容。
 
避免低效扩容
 
大部分情况下，动态扩容的hash表插入一个数据都很快，但特殊情况下，当装载因子达阈值，需先扩容，再插数据。这时，插入数据就会变得很慢！
 若hash表当前大小为1G，想扩容为原来2倍，就需对1G数据重新计算哈希值并从原hash表搬移到新表，听着都耗时！
 所以这时，“一次性”扩容机制就不合适了。
 
为避免一次性扩容耗时过多，可将扩容操作穿插在插入操作的过程中分批完成。当装载因子达阈值后，只申请新空间，但并不将老数据搬移到新hash表。
 
当有新数据插入，将新数据插入新hash表中，并从老原hash表拿出一个数据放入新hash表。
 每次插入一个数据到散列表，重复上面过程。
 经过多次插入操作之后，原hash表的数据就一点点都迁移至新hash表。这就不会一次性数据搬移，插入操作就都变得很快了。
 
 这期间的查询操作怎么做？
 为兼容新、老hash表数据，先查新hash表，没找到再去原hash表查找。
 
通过这样的均摊，将一次性扩容代价，均摊到多次插入操作，解决一次性扩容耗时过多问题。这时任何情况下，插入一个数据的时间复杂度都是O(1)。
 
应用
 
强大的 HashMap
 
1.初始大小
 HashMap默认的初始大小是16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高HashMap的性能。
 
2.装载因子和动态扩容
 最大装载因子默认是0.75，当HashMap中元素个数超过0.75*capacity（capacity表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
 
3.散列冲突解决方法
 HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。
 
于是，在JDK1.8版本中，为了对HashMap做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高HashMap的性能。当红黑树结点个数少于8个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
 
4.散列函数
 散列函数的设计并不复杂，追求的是简单高效、分布均匀。我把它摘抄出来，你可以看看。
 
int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}
 
其中，hashCode()返回的是Java对象的hash code。比如String类型的对象的hashCode()就是下面这样：
 
public int hashCode() {
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0) {
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}
 
单词拼写检查功能是如何实现的？
 
常用英文单词20万个，假设单词平均长度10个字母，平均一个单词占用10字节，那20万英文单词大约占2MB存储空间，这完全可以放在内存。所以我们可以用散列表来存储整个英文单词词典。
 
当用户输入某个英文单词时，拿用户输入的单词去散列表中查找：
 
查到，则说明拼写正确
没有查到，则说明拼写可能有误，给予提示
 
这就能轻松实现快速判断是否存在拼写错误。