參考資料：

[1]哈希沖突

思路：

哈希沖突是因為用鍵算出來的值作為地址去存放鍵值對祠墅，如果之前的值存在了难审，那么就擠一擠沙绝，這就是哈希沖突。
哈希沖突得用樹來解決亚再。
哈希表的時間復雜度理論上是O(1)郭膛。如果用樹實現(xiàn)的話，那就是樹的時間復雜度氛悬。
哈希表是一種比較復雜的數(shù)據(jù)結構则剃，C++標準模板庫中map和unordered_map實現(xiàn)了哈希表的功能，可以直接拿過來用如捅。不需要你實現(xiàn)哈希表的數(shù)據(jù)結構棍现。哈希表的鍵是字符，值是該字符出現(xiàn)的次數(shù)镜遣。

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：每掃描一個字符，就能從哈希表中得到該字符出現(xiàn)的次數(shù)
        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’字符

//第一個只出現(xiàn)一次的字符,返回該字符的位置
int FirstNotRepeatingChar(string sString)
{
    //把每字符出現(xiàn)的次數(shù)存入對應的位置上
        //必須進行初始化
    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;


}