题目描述(引自剑指offer)
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。
菜鸡与大佬的对话
菜鸡修炼坊
散列表(也称哈希表)，是唯一的专用于集合的数据结构。它通过将关键字值直接映射到表中的某个位置，将该关键字对应的数据元素存储在这个位置。查找时，可以直接根据被查找的关键字值找到存储该数据元素的地址，从而获得这个元素。
这里提到了一个非常有趣的概念——映射。在数学中，映射是指两个集合元素之间的对应关系。而在散列表中，则是指关键字值与数组下标的对应关系。具体的映射规则，被称为散列函数。
散列函数的引入不可避免地带来了哈希冲突的问题，即多个不同元素可能会被映射到同一个位置。
因此，掌握了如何设计散列函数，以及如何解决哈希冲突，也就掌握了如何实现散列表。
(1) 常用的散列函数包括直接定址法，除留余数法，数字分析法，平方取中法和折叠法等。
| 散列函数 | 定义 |
| 直接定址法 | 设关键字为x， 那么其散列地址为 H(x) = ax + b (a，b均为常数)。 |
| 除留余数法 | 设M是散列表的大小， 关键字为x， 那么其散列地址为 H(x) = x mod M。 |
| 数字分析法 | 若在关键字集合中，每个关键字均由n位数字组成(x1, x2, ... , xn)，分析关键字中的每一位数字的分布规律，并从中提取分布均匀的若干位或它们的组合作为地址。 |
| 平方取中法 | 如果关键字中各位的分布都比较均匀，但关键字的值域比数组规模大，则可以将关键字平方后，取其结果的中间各位作为散列函数值。 |
| 折叠法 | 如果数字的分布大体上是均匀的，则选取一个长度后，将关键字按此长度分组相加。 |
在实际应用中，采用何种散列函数，要考虑以下因素：
计算散列函数所需时间
关键字长度
散列表长度(散列地址范围)
关键字分布情况
记录的查询频率
总的原则是选取某个散列函数，使产生冲突的可能性尽量小。
(2) 解决冲突的方法有两种：闭散列表和开散列表。所谓的闭散列表是指将溢出元素存放到散列表中没有使用过的单元中去。而开散列表是指将映射到同一地址的数据元素分别存放到散列表以外的各自的线性表中去。详见下表。
| 解决冲突的方法 | 具体方案 | 定义 |
| 闭散列表 | 线性探测法 | 在该数组中从映射到的位置开始顺序搜索，直到发现空位置。 |
| 二次探测法 | 不是直接检查下一单元，而是检查远离初始探测点的某一单元，以消除线性探测中的初始聚集问题。 | |
| 再散列法 | 采用两个散列函数H1和H2。H1计算探测序列的起始地址，H2计算下一个探测位置的步长。 | |
| 开散列表 | 拉链法 | 将具有同一散列地址的元素都存储在一个单链表中。 |
题目分析
一番修炼之后，菜鸡向题目发起了挑战。机智的菜鸡发现题目中给出的字符串全部是由字母组成的，菜鸡隐隐觉得散列函数和字母的ASCII码脱不了干系。菜鸡心中清晰地记得，A-Z对应的ASCII码为65-90，而a-z对应的ASCII码值为97-122。于是，关键字值与数组下标的映射关系便浮出水面了。理顺思路之后，菜鸡决定用Java代码实现自己的心路历程。
代码实现
public class Solution {public int firstNotRepeatingChar(String str) {// 为了映射简便，故申请的数组长度为58而不是52int[] array = new int[58];for (int i = 0; i < str.length(); i++) {array[str.charAt(i) - 'A']++;}for (int i = 0; i < str.length(); i++) {if (array[str.charAt(i) - 'A'] == 1) {return i;}}return -1;}}
经过此次修炼，菜鸡对散列表有了一定的理解，散列表的重点是hash函数的选择和hash冲突的解决，菜鸡脑中的数据结构网又完善了一些……
