Probabilistic Data Structures (PDS) has been evolved as a potential solution for many applications in smart cities to complete this tedious task of handling big data with real-time response. PDS has been used in many smart city domains, including healthcare, transportation, the environment, energy, and industry. The goal of this paper is to provide a comprehensive review of PDS and its applications in the domains of smart cities. The prominent domain of the smart city has been explored in detail; origin, current research status, challenges, and existing application of PDS along with research gaps and future directions. The foremost aim of this paper is to provide a detailed survey of PDS in smart cities; for readers and researchers who want to explore this field; along with the research opportunities in the domains.