Inhomogeneous fluid solvation theory (IFST) and free energy perturbation (FEP) calculations were performed for a set of 20 solutes to compute the hydration free energies. We identify the weakness of histogram methods in computing the IFST hydration entropy by showing that previously employed histogram methods overestimate the translational and orientational entropies and thus underestimate their contribution to the free energy by a significant amount. Conversely, we demonstrate the accuracy of the k-nearest neighbors (KNN) algorithm in computing these translational and orientational entropies. Implementing the KNN algorithm within the IFST framework produces a powerful method that can be used to calculate free-energy changes for large perturbations. We introduce a new KNN approach to compute the total solute-water entropy with six degrees of freedom, as well as the translational and orientational contributions. However, results suggest that both the solute-water and water-water entropy terms are significant and must be included. When they are combined, the IFST and FEP hydration free energies are highly correlated, with an R(2) of 0.999 and a mean unsigned difference of 0.9 kcal/mol. IFST predictions are also highly correlated with experimental hydration free energies, with an R(2) of 0.997 and a mean unsigned error of 1.2 kcal/mol. In summary, the KNN algorithm is shown to yield accurate estimates of the combined translational-orientational entropy and the novel approach of combining distance metrics that is developed here could be extended to provide a powerful method for entropy estimation in numerous contexts.