参考资料：

[1]哈希冲突

思路：

哈希冲突是因为用键算出来的值作为地址去存放键值对，如果之前的值存在了，那么就挤一挤，这就是哈希冲突。
哈希冲突得用树来解决。
哈希表的时间复杂度理论上是O(1)。如果用树实现的话，那就是树的时间复杂度。
哈希表是一种比较复杂的数据结构，C++标准模板库中map和unordered_map实现了哈希表的功能，可以直接拿过来用。不需要你实现哈希表的数据结构。哈希表的键是字符，值是该字符出现的次数。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        //剑指OFFFER面试题50

        //步骤1：定义一个哈希表
        map<char,int> mp;

        //步骤2：每扫描一个字符，就在哈希表中对应项加1
        for(int i=0;i<str.size();i++)
        {
            mp[str[i]]++;
        }

        //步骤3：每扫描一个字符，就能从哈希表中得到该字符出现的次数
        for(int i=0;i<str.size();i++)
        {
            if(mp[str[i]] ==1)
                return i;
        }
        
        return -1;//return -1 是啥意思啊
    }
};

改进：

string类似于char类型的vector;
//char类型的和string类型的变量，后面都有‘\0’字符

//第一个只出现一次的字符,返回该字符的位置
int FirstNotRepeatingChar(string sString)
{
    //把每字符出现的次数存入对应的位置上
        //必须进行初始化
    int a[255] = {0};

    int nLen = sString.size();
    if (nLen == 0)
        return -1;


    for (int i = 0; i < nLen; i++)
    {
        a[sString[i]]++;

    }


    int nLocation;
    bool bFlag = false;
    for (int i = 0; i < nLen; i++)
    {
        if (a[sString[i]] == 1)
        {
            nLocation = i;
            bFlag = true;
            break;
        }
    }

    if (bFlag == true)
        return nLocation;
    else
        return -1;
}

char FirstNotRepeatingChar(char * cStr)
{
    if (*cStr == '\0')
        return NULL;
    int a[255] = {0};


    char* cStr2 = cStr;
    //以每个字符对应的作为索引
    while (*cStr2 != '\0')
    {
        a[*cStr2]++;
        cStr2++;
    }
    //回到原点
    cStr2 = cStr;
    bool bFlag = false;
    char cTarget;
    while (*cStr2 != '\0')
    {
        if (a[*cStr2] == 1)
        {
            bFlag = true;
            cTarget = *cStr2;
            break;
        }
        cStr2++;
    }

    if (bFlag == true)
        return cTarget;
    else
        return NULL;


}