Your question relates to the changing balance of power between Republicans and Democrats between the 1868 and 1876 Presidential elections, particularly in the southern United States. Your particular concern is the representation of African Americans in 1876, and whether possible suppression of their votes "unfairly" deprived Hayes of a popular vote majority to support his electoral college majority.
It is noteworthy that the total suffrage rose from 5.7 million in 1868 to 6.4 million in 1872 8.3 million in 1876. (This is for the two major parties and excludes "splinter" candidates' votes.) During this time, the Republican vote rose from 3.0 million to 4.1 million, or 1.1 million, while the Democratic vote rose from 2.7 million to 4.2 million, or 1.5 million.
Most of the difference in the Democratic vote rise came in the southern states. The issue was that in 1868, many whites, were unable to vote, either because their individual states had not been reconstructed, or because the voters themselves had not taken the loyalty oaths or whatever was needed to establish themselves as voters. By 1876, whites had fully regained their suffrage.
I'm going to use a simplifying assumption: That most southern white voters voted Democratic, and that most black voters voted Republican, unless otherwise specified. So looking at only the southern states, I divide them into three groups. 1) states where the percentage of the Democratic voters exceeded the percentage of whites (the states of concern), 2) states where the percentage of the Democratic vote in 1876 approximated the percentage of whites, and 3) "special cases" where the percentage of the Democratic vote in 1876 was much less than the percentage of whites were much less than the percentage of Democratic voters.
In South Carolina, for example, the white population in 1870 was "only" 41%, but the Democrats won almost 50% of the vote in 1876 (versus 24% in 1872). This represented a huge surge and disproportion in the Democratic vote, reflecting, among other things, a 101% turnout of eligible voters, as pointed out by T.E.D. Such "ballot-stuffing" also suggests activity of the opposite kind, suppression of the "wrong" votes.
The remaining states that show similar patterns, are presented as State (whites as % of population, 1876 Democratic percentage, 1872 Democratic percentage). Similar patterns existed in Georgia (54%, 72%,54%); Alabama (52%, 60%, 47%), and Mississippi (46%, 68%, 47%). These states' 1872 Democratic vote percentage were more or less in line with their percentage of whites, the disparity occurred in 1876;
Of less concern are states in the second category, They are: Virginia (56%, 60%,59%); Louisiana (50%, 48%, 44%), and Texas (69%,70%. 59%).
In the last group are states where whites voted Republican in significant numbers, meaning that the Democratic share of the vote was much less than the white population. North Carolina (63%, 54%, 42%), Arkansas (76%, 66%, 48%), Tennessee (77%, 60%,52%), and Kentucky (82%, 61%,52%).
Sources: 1870 census. Wikipedia articles for Presidential elections in 1868, 1872, and 1876.